TRPL

We discussed this today.

In the FWD use cases, conversion (incremental and full) is likely to be massively impacted by this. Runtime (dynamic queries) will likely see less benefit.

One thing that was really holding me back on this was my perception that we needed to use the database as a persistence mechanism for ASTs. As Constantin and Alex pointed out, this could just be an indexing mechanism and we could leave the ASTs in the filesystem. That idea has the very nice outcome of decoupling this task from the database back storage implementation of #1759 and related tasks. What always bothered me that the the table structures of an RDBMS are a poor fit for representing a tree structure of arbitrary depth.

So the high level plan here:

1. Implement a database (with one or more tables as needed) that stores the most critical values of an AST node. The design objective is to cover the most commonly used expression elements.
2. Modify our AST maintenance code to update the database when these values are created, edited or deleted. We can't just do this once on creation or the "index" would not represent the real state of the ASTs.
3. Write an analyzer for TRPL expressions that can translate expressions into SQL queries against this database. The result of the queries is the list of AST nodes that meet the WHERE clause criterion. The result set should be sorted to ensure that the nodes would be walked in the same order that they would be encountered by the traditional TRPL walk. The processing should be able to run across the entire project or just a subset of ASTs (e.g. incremental conversion).
4. Rework the PatternEngine to implement an alternate walk for a rule container (and any contained rules) when the SQL approach is available. SQL processing is only available if all of the expression can be converted into a SQL query. Anything that is not fully supported will just execute as before.
5. (optional) Rework TRPL rules so that the top level rules of all files can be fully supported in SQL mode.

Modify our AST maintenance code to update the database when these values are created, edited or deleted. We can't just do this once on creation or the "index" would not represent the real state of the ASTs.

AFAIK, you can't change the AST that is walked real-time. You have a copy of the AST that is walked. So, we need to handle the updates of the DB only at the end of AST traversal. This can be done using two DB connections: one DB connection is used for read and the other for write. When the walk is over, we commit the write connection. Otherwise, we can use a special transaction isolation level to ensure than on a single connection, but this may not be generally available to any DB vendor.

Also, many rules have annotation checks, so we need to think of a way to also handle these.

Rework the PatternEngine to implement an alternate walk for a rule container (and any contained rules) when the SQL approach is available. SQL processing is only available if all of the expression can be converted into a SQL query. Anything that is not fully supported will just execute as before.

I thought of this a bit longer. If we gather a list of ASTs for each rule, then we still have to check for each AST if it belongs to that set. I think this is faster than actually running the expression, but it still has to go through all rules to check inclusion. Considering this technique is feasible only for static rules (without evalLib or more complex clauses), are we sure that emitting a SQL + doing a set inclusion check for each rule is faster than running the expression for each AST?

The original theoretical complexity we have is O(AST_COUNT * RULE_COUNT * AVG_EXPR_CHECK). With the proposed technique: O(AST_COUNT * DB_UPDATE + RULE_COUNT * AVG_DB_LOOKUP + AST_COUNT * RULE_COUNT * AVG_INCLUSION). Note that this does not include evalLib expressions. So, we pay the extra O(AST_COUNT * DB_UPDATE + RULE_COUNT * AVG_DB_LOOKUP) for the optimization of O(AST_COUNT * RULE_COUNT * (AVG_EXPR_CHECK - AVG_INCLUSION)). I guess the AVG_INCLUSION can be a BitSet look-up which is very fast.

To be fair, my first proposal was to index on TRPL rule instead of AST. So, the data structure (I thought of a simple map initially, but it can work with DB as well) will store the TRPL rules: type assertion, parent type assertion, etc. When we reach a certain AST, we query the DB for the ordered set of rules to apply. With this list, we simply iterate it and execute rules one-by-one without other checks. The POC would be such DB with an index on type. If we have a "BUFFER" node, we emit select * from rule where (rule.type = 'buffer' or rule.type is null) order by rule.order asc (is null represents rules without type assertion). Considering type is indexed, it will be fast.

With this proposed technique: O(RULE_COUNT * DB_UPDATE + AST_COUNT * AVG_DB_LOOKUP + AST_COUNT * REDUCED_RULE_COUNT * AVG_EXPR_CHECK). I guess the filtering level of this solution is more empiric and weaker than indexed AST variant.

TL;DR I don't think that any DB solutions will evaluate the expressions faster than we already do in TRPL. The only shiny thing here is the indexing and the hope that we can reduce the number of expressions to be executed. However, the provided solution seem to keep the number of expressions, but reduce the complexity for executing the expr to having an inclusion check with the price of computing sets of ASTs for each rule. Example:

<rule>type == prog.system_dialog_font

• currently we check this expression for each AST
• with OG proposed solution, we emit a query in the AST DB for select ast.id from ast where type = 'system_dialog_font' once and gather the AST ids (which might be empty). For ALL ASTS we will do a bitset.get(astId). We can remove the rule if the return list is empty, but we still have to execute the query even if there is no system_dialog_font AST. Also, we have to store all ASTs in the DB and bitsets in memory for this to work.
• with my empiric solution, we emit a query in the rule DB for select rule.order from rule where (type_assertion = 'system_dialog_font' or type_assertion is null) order by rule.order asc if we ever have a system_dialog_font AST. We need to store only the rules in the DB. For this specific query, we can even cache the results, SO any AST of type system_dialog_font will re-use the same rule list. The bad part is that we have to re-evaluate the conditions for each rule as the rules may have some and conditions afterwards.

From IDE POV, we also need to have a way to reconvert fast one single file after an update. If the IDE user changes one line of a big file:

• the AST DB idea would need to rebuild the AST DB, so pay the price of the optimization on each file change + execute the SQLs for each rule + fetch the bitsets and apply rules.
  • I don't see room for improvement here, unless we can incrementally convert a single file.
  • what can we reuse from one file to another?
• the rules DB idea would not need to rebuilt the DB, because the rule set is static. More than this, the queries should not be re-executed considering their result-set is cached.
  • this attempt is focused around carrying information around from one file to another, mapping AST patterns to rule lists.

PS: There is also #1747 that I had in mind yesterday. If we think of:

<rule>type == prog.system_dialog_font

to be transformed in:

rule(ast => ast.type == prog.system_dialog_font, ast => // rule body)

then we loose the expression structure to be used on the AST DB. We would have to transform it into:

rule("type = system_dialog_font", ast => // rule body)

in order to keep the TRPL or SQL expression as a String or with typing:

rule(TypeMatch(SYSTEM_DIALOG_FONT), ast => // rule body)

considering we can have more complex Or(TypeMatch(SEEK), Parent(TypeMatch(STATEMENT))). However, it can get quite tedious for complex expressions:

<rule>evalLib("call_to_user_defined_function", copy) or (evalLib("oo_call_type", copy, null) and !evalLib("new_object", copy) and !evalLib("type_pair", copy, prog.func_poly, prog.kw_dyn_invk)) or (type == prog.expression and upPath(this, prog.kw_run, prog.lparens, prog.parameter))

to:

Or(                                                                                           
      EvalLib("call_to_user_defined_function"),                                                                                         
      And(                                                                                                                              
        EvalLib("oo_call_type", null),                                                                                                  
        Not(EvalLib("new_object")),                                                                                                     
        Not(EvalLib("type_pair", prog.func_poly, prog.kw_dyn_invk))                                                                     
      ),
      And(                                                                                                                              
        TypeMatch(prog.expression),                                                               
        UpPath(prog.kw_run, prog.lparens, prog.parameter)                                                                               
      )
    )

especially as these won't reach the SQL anyway. So I would imagine that sooner rather than latter we would have a more convenient

def rule(condition: Condition, action: AST => Unit): Unit
def rule(condition: Condition, dynamicCondition: AST => Boolean, action: AST => Unit): Unit

But if that happens, the extra mile would be:

def rule(type: TypeCondition, action: AST => Unit): Unit
def rule(condition: TypeCondition, dynamicCondition: AST => Boolean, action: AST => Unit): Unit

where TypeCondition would allow specifying a typed expression like Or(SEEK, UpPath(DEFINE, STATEMENT)).

So, the indexing can be done directly through the native overloads:

rule(Or(SEEK, UpPath(DEFINE, STATEMENT)), ast => // rule body

• OR would eventually save the rule body in the SEEK bucket and in the UpPath(DEFINE, STATEMENT) bucket.

rule(And(SEEK, Parent(STATEMENT)), ast => // rule body

• AND would eventually resolve to UpPath (UpPath(SEEK, STATEMENT)))

It is important to acknowledge the "one type per AST invariant", because, this way, the OR and AND logicals can be easily resolved.

Ultimately, if a SEEK AST will be reached, we will check the SEEK bucket and run the dynamicCondition if any for each rule.

Lastly, I am insisting on this point, because the AST SQL would be possible for a slim set of constructs:

• types can be saved in DB and queried.
• annotations can be technically saved in DB, but there are tons of annotations triggering many many boolean columns. Even so, we won't be able to index on all of them, so the DB engine will do filtering on these (just like we would do in TRPL), so I won't imagine there will be an evident gain.
• evalLib can't be resolved by DB.

So my concern is that the AST DB might help us only with types in the end, but the infrastructure for it would be too complex.

AFAIK, you can't change the AST that is walked real-time. You have a copy of the AST that is walked. So, we need to handle the updates of the DB only at the end of AST traversal. This can be done using two DB connections: one DB connection is used for read and the other for write. When the walk is over, we commit the write connection. Otherwise, we can use a special transaction isolation level to ensure than on a single connection, but this may not be generally available to any DB vendor.

Yes, the database would only have to be updated when we refresh this from copy. Until then we can gather edits in copy and then flush them all at once.

my first proposal was to index on TRPL rule instead of AST. So, the data structure (I thought of a simple map initially, but it can work with DB as well) will store the TRPL rules: type assertion, parent type assertion, etc. When we reach a certain AST, we query the DB for the ordered set of rules to apply. With this list, we simply iterate it and execute rules one-by-one without other checks

I don't understand how we could maintain the control flow of a TRPL rule set in this concept. Whether a particular rule matters or not is completely dependent upon the containing rules that have been matched (or not matched, or iterated) as well as the walk type (init, descent, next-child, walk, ascent, post). TRPL rule-sets are programs. Splitting the program logic into DB rows and trying to put the control flow back together seems way complicated if it is even possible.

The core idea here is that the majority of the value is in replacing the outermost rules with the DB lookup of the very limited number of possible matches. In a project with 10MLOC across 10k files (1KLOC/file) there are probably something like 70 million ASTs. Many outermost rules may only match a very small number of ASTs (10s, 100s) out of these millions. Even the rules with a high hit rate (10000s) will only be a very very small percentage of the total number of ASTs. The outermost rules are the ones where today they get walked for all 70 million ASTs. Rules contained inside, only get walked for those AST nodes that matched in the outer rules, so they are already very limited in the number of executions.

We would have to figure out ways to handle the common expression elements. I don't think type on its own is enough. Text, common annotations would be important too. The really tricky part is the tree structure matching, which is incredibly important. We'd have to figure out how to represent these. SQL is certainly a poor tool for that purpose.

I don't understand how we could maintain the control flow of a TRPL rule set in this concept. Whether a particular rule matters or not is completely dependent upon the containing rules that have been matched (or not matched, or iterated) as well as the walk type (init, descent, next-child, walk, ascent, post). TRPL rule-sets are programs. Splitting the program logic into DB rows and trying to put the control flow back together seems way complicated if it is even possible.

I meant the same approach as for AST views. We keep only views / abstract representations of the rules. I would imagine a table with (order int not null, type_requirement int, parent_type_requirement int, rule_id int not null). The rule_id will map this representation to the actual TRPL rule body. It can have more columns (e.g. parent of parent, certain popular annotation requirements, etc.).

Also, just like for the AST DB idea, we would store only the top-level rules.

The core idea here is that the majority of the value is in replacing the outermost rules with the DB lookup of the very limited number of possible matches. In a project with 10MLOC across 10k files (1KLOC/file) there are probably something like 70 million ASTs. Many outermost rules may only match a very small number of ASTs (10s, 100s) out of these millions. Even the rules with a high hit rate (10000s) will only be a very very small percentage of the total number of ASTs. The outermost rules are the ones where today they get walked for all 70 million ASTs. Rules contained inside, only get walked for those AST nodes that matched in the outer rules, so they are already very limited in the number of executions.

Completely agreed and this is what I think that indexing ASTs may go badly. The AST traversal would still be DFS, so the order of the rule processing should be in the order of the DFS. With that being said, once a sub-tree is reached, how do we know which rules to apply? Querying the AST DB with the TRPL expression as SQL would yield a list of AST for each rule, not a list of rules for the AST. For each rule, we would store a set or bitset of ASTs that match. So, for a certain sub-tree, we would still have to go through all rules to check if the AST is part of the set or bitset for that rule. It doesn't leverage the "very limited number of possible matches" observation.

And this is why I made the overvations:

are we sure that emitting a SQL + doing a set inclusion check for each rule is faster than running the expression for each AST?

So my concern is that the AST DB might help us only with types in the end, but the infrastructure for it would be too complex.

Alexandru Lungu wrote:

I don't understand how we could maintain the control flow of a TRPL rule set in this concept. Whether a particular rule matters or not is completely dependent upon the containing rules that have been matched (or not matched, or iterated) as well as the walk type (init, descent, next-child, walk, ascent, post). TRPL rule-sets are programs. Splitting the program logic into DB rows and trying to put the control flow back together seems way complicated if it is even possible.

I meant the same approach as for AST views. We keep only views / abstract representations of the rules. I would imagine a table with (order int not null, type_requirement int, parent_type_requirement int, rule_id int not null). The rule_id will map this representation to the actual TRPL rule body. It can have more columns (e.g. parent of parent, certain popular annotation requirements, etc.).

Sorry, I still don't understand. A TRPL rule-set is a program designed as a set of callbacks based on the event type (init, walk...). The program (i.e. the rules for that event) is executed based on the movement through the AST. If the rule expressions (which are translated into SQL) have no side-effects, then we can avoid a great deal of unnecessary processing of we only execute the contained rules for a small number of AST nodes.

I don't see how calculating the rules which an AST may match. In other words, the rules define the control flow and they must execute based on the structure of that TRPL rule-set. It isn't just about an ordering of the rules, the logical flow of the rules must be matched. I think that doesn't translate into the calculation of a view.

The concept of a view in TRPL is a list of ASTs that are processed. It isn't a list of rules that are processed.

Completely agreed and this is what I think that indexing ASTs may go badly. The AST traversal would still be DFS, so the order of the rule processing should be in the order of the DFS. With that being said, once a sub-tree is reached, how do we know which rules to apply?

In my proposed approach, we process each rule as we do today. The difference is that it only needs to be processed for a very small number of nodes. We are calculating the specific nodes that will be processed by the contained rules for the given topmost rule that was matched.

Yes, we need to order these matched executions in the same order they would have been reached by the DFS event model walking.

Querying the AST DB with the TRPL expression as SQL would yield a list of AST for each rule, not a list of rules for the AST.

Good. That is what we want. I don't see how a list of rules is helpful.

Correct me if I am wrong on the following simplistic example:

• we have an AST named root and two children named leaf1 and leaf2.
• we have 3 walk top level rules in a rule-set. each one has different conditions.

The processing will go like:

• for root:
  • check rule 1 condition; if it matches, the run the contained actions/rules.
  • check rule 2 condition; if it matches, the run the contained actions/rules.
  • check rule 3 condition; if it matches, the run the contained actions/rules.
• then go to leaf1:
  • check rule 1 condition; if it matches, the run the contained actions/rules.
  • check rule 2 condition; if it matches, the run the contained actions/rules.
  • check rule 3 condition; if it matches, the run the contained actions/rules.
• then go to leaf2
  • check rule 1 condition; if it matches, the run the contained actions/rules.
  • check rule 2 condition; if it matches, the run the contained actions/rules.
  • check rule 3 condition; if it matches, the run the contained actions/rules.

In my proposed approach, we process each rule as we do today. The difference is that it only needs to be processed for a very small number of nodes. We are calculating the specific nodes that will be processed by the contained rules for the given topmost rule that was matched.

From my understanding, the processing will go like:

• compute AST DB; insert root, leaf1 and leaf2 views (text, type, parent type, maybe annotations, etc.)
• for each rule (i.e. 1, 2, 3) execute an SQL with its condition to fetch the list of AST for which the rule matches.
  • from now on, we have a map {rule1 -> [root], rule2 -> [root, leaf2], rule3 -> [leaf2]}
• for root:
  • check rule 1 set; root is part of it, so run the contained actions/rules.
  • check rule 2 set; root is part of it, so run the contained actions/rules.
  • check rule 3 set; root it not part of it.
• then go to leaf1:
  • check rule 1 set; leaf1 is not part of it.
  • check rule 2 set; leaf1 is not part of it.
  • check rule 3 set; leaf1 it not part of it.
• then go to leaf2
  • check rule 1 set; leaf2 is not part of it.
  • check rule 2 set; leaf2 is part of it, so run the contained actions/rules.
  • check rule 3 set; leaf2 is part of it, so run the contained actions/rules.

Please correct me if my understanding is wrong. ATM, each AST will still go through all rules. It won't execute their condition, but there will still be inclusion checks.

From my understanding, the processing will go like:

• compute AST DB; insert root, leaf1 and leaf2 views (text, type, parent type, maybe annotations, etc.)

I'm not sure what you mean by "compute AST DB". I would expect that the DB inserts occur during parsing. More inserts, updates or deletions might occur when this is reset from copy.

Yes, there will be some list of data that is inserted or updated in the table.

Please correct me if my understanding is wrong. ATM, each AST will still go through all rules. It won't execute their condition, but there will still be inclusion checks.

I don't see it this way. I think we would calculate the "effective walk", the minimum set of nodes + events that would match and which need to be executed. In your example, which are presumably all walk rules, you mention that from now on, we have a map {rule1 -> [root], rule2 -> [root, leaf2], rule3 -> [leaf2]} so we would execute:

• the contents of rule1 with root as this/copy
• the contents of rule2 with root as this/copy
• the contents of rule2 with leaf2 as this/copy
• the contents of rule3 with leaf2 as this/copy

I don't see why we ever need to do more than that. Isn't this the equivalent of the full walk? In a real scenario, we would also have to take into account the event type.

I'm not sure what you mean by "compute AST DB". I would expect that the DB inserts occur during parsing. More inserts, updates or deletions might occur when this is reset from copy.

I mean the DB where we store the AST views. This is built before-hand after parsing and reset after each phase (copy -> this).

I think we would calculate the "effective walk", the minimum set of nodes + events that would match and which need to be executed.

This is something interesting I did not account for:

• consider map: {rule1 -> [root], rule2 -> [root, leaf2], rule3 -> [leaf2]}
  • iterate rule1 list: add rule1 to the list of rules for root
  • iterate rule2 list: add rule2 to the list of rules for root and leaf2
  • iterate rule3 list: add rule3 to the list of rules for leaf2
  • now we have the other map {root -> [rule1], leaf1 -> [], leaf2 -> [rule2, rule3]}

So, there will be an step where we actually retrieve the rules list per AST from the AST list per rule. Is this right?

I don't see why we ever need to do more than that. Isn't this the equivalent of the full walk?

What I wanted to stress all along is that, for something like:

{rule1 -> [root], rule2 -> [root, leaf2], rule3 -> [leaf1]} (note that rule3 is now for only for leaf1)

You can't presume that:

• the contents of rule1 with root as this/copy
• the contents of rule2 with root as this/copy
• the contents of rule2 with leaf2 as this/copy
• the contents of rule3 with leaf1 as this/copy

is correct any longer. Applying rule3 for leaf1 after applying rule2 for leaf2 is incorrect. So, the sorting shall be done after the AST (DFS order) rather than rule. This is not something granted by the SQLs.
So we have to reorder at Java side the contents retrieved from the DB.

In a real scenario, we would also have to take into account the event type.

Of course, I simplified examples for a single event type (e.g. walk). This algorithm is applied per-AST / per-event.

What I wanted to stress all along is that, for something like:

{rule1 -> [root], rule2 -> [root, leaf2], rule3 -> [leaf1]} (note that rule3 is now for only for leaf1)

You can't presume that:

• the contents of rule1 with root as this/copy
• the contents of rule2 with root as this/copy
• the contents of rule2 with leaf2 as this/copy
• the contents of rule3 with leaf1 as this/copy

is correct any longer. Applying rule3 for leaf1 after applying rule2 for leaf2 is incorrect.

Yes, we would calculate the "effective walk" for each newly loaded tree. The results will differ by tree.

So, the sorting shall be done after the AST (DFS order) rather than rule.

Correct.

This is not something granted by the SQLs.

Well, some of it should be naturally represented because we can sort by the AST IDs (which are always increasing starting at the root).

Because during parsing we essentially match and create on a DFS basis, the AST IDs naturally sort this way.

...
    <ast col="0" id="339302416386" line="0" text="statement" type="STATEMENT">
      <ast col="1" id="339302416387" line="55" text="DEFINE" type="DEFINE_VARIABLE">
        <annotation datatype="java.lang.Boolean" key="undoable" value="false"/>
        <annotation datatype="java.lang.String" key="name" value="appSrvUtils"/>
        <annotation datatype="java.lang.Long" key="support_level" value="16400"/>
        <annotation datatype="java.lang.Long" key="peerid" value="1271310319701"/>
        <annotation datatype="java.lang.Boolean" key="shared" value="true"/>
        <annotation datatype="java.lang.String" key="javaname" value="appSrvUtils"/>
        <annotation datatype="java.lang.String" key="classname" value="handle"/>
        <annotation datatype="java.lang.Boolean" key="newed" value="true"/>
        <annotation datatype="java.lang.Boolean" key="vardef" value="true"/>
        <annotation datatype="java.lang.Boolean" key="global" value="true"/>
        <annotation datatype="java.lang.Boolean" key="promote" value="true"/>
        <annotation datatype="java.lang.Long" key="type" value="391"/>
        <ast col="8" id="339302416397" line="55" text="NEW" type="KW_NEW"/>
        <ast col="12" id="339302416399" line="55" text="GLOBAL" type="KW_GLOBAL"/>
        <ast col="19" id="339302416401" line="55" text="SHARED" type="KW_SHARED"/>
        <ast col="35" id="339302416405" line="55" text="appSrvUtils" type="SYMBOL"/>
        <ast col="47" id="339302416407" line="55" text="AS" type="KW_AS">
          <ast col="50" id="339302416409" line="55" text="HANDLE" type="KW_HANDLE"/>
        </ast>
        <ast col="72" id="339302416411" line="55" text="NO-UNDO" type="KW_NO_UNDO"/>
      </ast>
    </ast>
    <ast col="0" id="339302416414" line="0" text="statement" type="STATEMENT">
      <ast col="1" id="339302416415" line="58" text="IF" type="KW_IF">
        <annotation datatype="java.lang.Long" key="support_level" value="16400"/>
        <annotation datatype="java.lang.Long" key="peerid" value="1271310319707"/>
        <ast col="0" id="339302416417" line="0" text="expression" type="EXPRESSION">
          <annotation datatype="java.lang.Long" key="support_level" value="16400"/>
          <annotation datatype="java.lang.Long" key="peerid" value="1271310319708"/>
          <ast col="4" id="339302416418" line="58" text="NOT" type="KW_NOT">
            <annotation datatype="java.lang.Long" key="support_level" value="16400"/>
            <annotation datatype="java.lang.Long" key="peerid" value="1271310319709"/>
            <ast col="8" id="339302416420" line="58" text="VALID-HANDLE" type="FUNC_LOGICAL">
...

We will need to look at that to ensure we get it right AND we need to handle the event properly because some of those must simulate traversals between specific IDs.

So we have to reorder at Java side the contents retrieved from the DB.

Could be, we'll have to see what we need to do here to get the effective walk to properly match the explicit walk we do today.

Could be, we'll have to see what we need to do here to get the effective walk to properly match the explicit walk we do today.

All clear. Thank you for the patience. I talked with Danut and Octavian yesterday to take a look on this as well before the IDE meeting.