Description

This addresses performance issues raised by our performance testing on two rules from MISRA C 2012.

Rule 5.8

Per the commit message:

 The performance fix is to:
     (a) Create a predicate which represents all the conflicting identifiers
         by simply counting the number of declarations and confirming at
         least one such declaration is external.
     (b) Use this to create a result table of Declarations that conflict
         with those identifiers.
     (c) Implement a "non unique" external identifier class that provides a
         member predicate to get all the conflicting declarations.
    
    The key point here is to prevent the optimiser from doing a join between
    Declaration.getName() and Declaration.getName(). Instead, the join is
    between the names of the non-unique external identifiers and the much
    smaller table of declarations that conflict with at least one such
    entry

Rule 8.7

Per the commit message:

    Performance is improved with the following changes:
     (a) Factoring out a predicate for the repeated calls to getTarget(), to
         avoid duplication and to create a semantically meaningful predicate
         which gets the target for a reference to an external identifier.
     (b) Use the factored out predicate to refine the reference class to
         only be references to external identifiers. This reduces the size
         of the class.
     (c) Create a predicate for computing a table of external identifiers,
         references to those identifiers and the translation units those
         exist in. We can then compute this table once, and use it in both
         the "find me a reference to this external identifier" case and in
         the "where the external identifier is not referenced in any other
         translation unit" case.
    
    Part (c) is the critical change. Without that, the optimizer was
    creating an expensive join order in the negation case, where it
    was effectively creating a cross product of all references to each
    external identifier, before later excluding on the negation. The use
    of our predicate in the negation case means we can first create a table
    of external identifiers and translation units, then apply that in the
    negation case without cross producting the references.

Change request type

• Release or process automation (GitHub workflows, internal scripts)
• Internal documentation
• External documentation
• Query files (.ql, .qll, .qls or unit tests)
• External scripts (analysis report or other code shipped as part of a release)

Rules with added or modified queries

• No rules added
• Queries have been added for the following rules:
  • rule number here
• Queries have been modified for the following rules:
  • Rule 5.8
  • Rule 8.7

Release change checklist

A change note (development_handbook.md#change-notes) is required for any pull request which modifies:

• The structure or layout of the release artifacts.
• The evaluation performance (memory, execution time) of an existing query.
• The results of an existing query in any circumstance.

If you are only adding new rule queries, a change note is not required.

Author: Is a change note required?

• Yes
• No

🚨🚨🚨
Reviewer: Confirm that format of shared queries (not the .qll file, the
.ql file that imports it) is valid by running them within VS Code.

• Confirmed

Reviewer: Confirm that either a change note is not required or the change note is required and has been added.

• Confirmed

Query development review checklist

For PRs that add new queries or modify existing queries, the following checklist should be completed by both the author and reviewer:

Author

• Have all the relevant rule package description files been checked in?
• Have you verified that the metadata properties of each new query is set appropriately?
• Do all the unit tests contain both "COMPLIANT" and "NON_COMPLIANT" cases?
• Are the alert messages properly formatted and consistent with the style guide?
• Have you run the queries on OpenPilot and verified that the performance and results are acceptable?
  As a rule of thumb, predicates specific to the query should take no more than 1 minute, and for simple queries be under 10 seconds. If this is not the case, this should be highlighted and agreed in the code review process.
• Does the query have an appropriate level of in-query comments/documentation?
• Have you considered/identified possible edge cases?
• Does the query not reinvent features in the standard library?
• Can the query be simplified further (not golfed!)

Reviewer

• Have all the relevant rule package description files been checked in?
• Have you verified that the metadata properties of each new query is set appropriately?
• Do all the unit tests contain both "COMPLIANT" and "NON_COMPLIANT" cases?
• Are the alert messages properly formatted and consistent with the style guide?
• Have you run the queries on OpenPilot and verified that the performance and results are acceptable?
  As a rule of thumb, predicates specific to the query should take no more than 1 minute, and for simple queries be under 10 seconds. If this is not the case, this should be highlighted and agreed in the code review process.
• Does the query have an appropriate level of in-query comments/documentation?
• Have you considered/identified possible edge cases?
• Does the query not reinvent features in the standard library?
• Can the query be simplified further (not golfed!)