Commit Graph

41159 Commits

Author SHA1 Message Date
Taus
b98c482c47 Python: Fix bad join in MRO flatten_list
This bad join was identified by the join-order-badness report, which
showed that:

py/use-of-input:MRO::flatten_list#f4eaf05f#fff#9c5fe54whnlqffdgu65vhb8uhpg# (order_500000)

calculated a whopping 212,820,108 tuples in order to produce an output of
size 55516, roughly 3833 times more effort than needed.

Here's a snippet of the slowest iteration of that predicate:
```
Tuple counts for MRO::flatten_list#f4eaf05f#fff/3@i1839#0265eb3w after 14ms:
0     ~0%     {3} r1 = JOIN MRO::need_flattening#f4eaf05f#f#prev_delta WITH MRO::ConsList#f4eaf05f#fff#reorder_2_0_1#prev ON FIRST 1 OUTPUT Rhs.1, Lhs.0 'list', Rhs.2
0     ~0%     {3} r2 = JOIN r1 WITH MRO::ClassList::length#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.2, Lhs.1 'list', Rhs.1 'n'
0     ~0%     {3} r3 = JOIN r2 WITH MRO::ClassListList::flatten#dispred#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.1 'list', Lhs.2 'n', Rhs.1 'result'

0     ~0%     {3} r4 = SCAN MRO::ConsList#f4eaf05f#fff#prev_delta OUTPUT In.2 'list', In.0, In.1
0     ~0%     {3} r5 = JOIN r4 WITH MRO::need_flattening#f4eaf05f#f#prev ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.0 'list'
0     ~0%     {3} r6 = JOIN r5 WITH MRO::ClassList::length#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.1, Lhs.2 'list', Rhs.1 'n'
0     ~0%     {3} r7 = JOIN r6 WITH MRO::ClassListList::flatten#dispred#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.1 'list', Lhs.2 'n', Rhs.1 'result'

0     ~0%     {3} r8 = r3 UNION r7

26355 ~2%     {3} r9 = SCAN MRO::ConsList#f4eaf05f#fff#prev OUTPUT In.2 'list', In.0, In.1

0     ~0%     {3} r10 = JOIN r9 WITH MRO::need_flattening#f4eaf05f#f#prev ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.0 'list'
0     ~0%     {3} r11 = JOIN r10 WITH MRO::ClassList::length#f0820431#ff#prev_delta ON FIRST 1 OUTPUT Lhs.1, Lhs.2 'list', Rhs.1 'n'
0     ~0%     {3} r12 = JOIN r11 WITH MRO::ClassListList::flatten#dispred#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.1 'list', Lhs.2 'n', Rhs.1 'result'
...
```
(... and a bunch more lines. The same construction appears several times,
but the join order is the same each time.)

Clearly it would be better to start with whatever is in `need_flattening`,
and then do the other joins. This is what the present fix does (by
unbinding `list` in all but the `needs_flattening` call).

After the fix, the slowest iteration is as follows:

```
Tuple counts for MRO::flatten_list#f4eaf05f#fff/3@i2617#8155ab3w after 9ms:
0 ~0%     {2} r1 = SCAN MRO::need_flattening#f4eaf05f#f#prev_delta OUTPUT In.0 'list', In.0 'list'

0 ~0%     {3} r2 = JOIN r1 WITH MRO::ConsList#f4eaf05f#fff#reorder_2_0_1#prev ON FIRST 1 OUTPUT Rhs.1, Lhs.1 'list', Rhs.2
0 ~0%     {3} r3 = JOIN r2 WITH MRO::ClassList::length#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.2, Lhs.1 'list', Rhs.1 'n'
0 ~0%     {3} r4 = JOIN r3 WITH MRO::ClassListList::flatten#dispred#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.1 'list', Lhs.2 'n', Rhs.1 'result'

1 ~0%     {2} r5 = SCAN MRO::need_flattening#f4eaf05f#f#prev OUTPUT In.0 'list', In.0 'list'

0 ~0%     {3} r6 = JOIN r5 WITH MRO::ConsList#f4eaf05f#fff#reorder_2_0_1#prev_delta ON FIRST 1 OUTPUT Rhs.1, Lhs.1 'list', Rhs.2
0 ~0%     {3} r7 = JOIN r6 WITH MRO::ClassList::length#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.2, Lhs.1 'list', Rhs.1 'n'
0 ~0%     {3} r8 = JOIN r7 WITH MRO::ClassListList::flatten#dispred#f0820431#ff#prev ON FIRST 1 OUTPUT Lhs.1 'list', Lhs.2 'n', Rhs.1 'result'
...
```
(... and so on. The remainder is 0 tuples all the way.)

In total, we went from
```
40.6s |  7614 |  15ms @ 1839 | MRO::flatten_list#f4eaf05f#fff@0265eb3w
```
to
```
7.8s |  7614 |  11ms @ 2617 | MRO::flatten_list#f4eaf05f#fff@8155ab3w
```
2022-06-28 14:17:47 +00:00
Paolo Tranquilli
5c6ac2a5f2 Swift: accept test results 2022-06-28 16:15:05 +02:00
Geoffrey White
63376da90f Swift: Add tests for LogicalOperaion.qll. 2022-06-28 15:04:47 +01:00
Paolo Tranquilli
6ff45d3dbe Merge main into redsun82/swift-enum-is-case 2022-06-28 16:03:38 +02:00
Brandon Stewart
c7b4133fbe Merge branch 'main' into patch-1 2022-06-28 09:46:46 -04:00
Paolo Tranquilli
364085a596 Swift: add DotSyntaxCallExpr tests 2022-06-28 15:44:42 +02:00
AlexDenisov
c4c3a52804 Merge pull request #9730 from github/redsun82/swift-trap-newlines
Swift: add missing newlines in trap
2022-06-28 15:41:05 +02:00
Ian Lynagh
3026456a39 Kotlin: Make more methods private 2022-06-28 14:38:13 +01:00
Paolo Tranquilli
7175869518 Swift: add missing newlines in trap
This is mostly cosmetic and for debugging, as the trap importer is
perfectly happy with trap entries on the same line without spaces
between them.
2022-06-28 15:17:18 +02:00
Henry Mercer
a7bd2030b6 Address review comments 2022-06-28 13:52:26 +01:00
Brandon Stewart
33d1aae92a Update ruby/ql/lib/codeql/ruby/frameworks/ActiveRecord.qll
Co-authored-by: Harry Maclean <hmac@github.com>
2022-06-28 08:51:01 -04:00
Brandon Stewart
1dc26a0ca3 Update ruby/ql/lib/codeql/ruby/frameworks/ActiveRecord.qll
Co-authored-by: Harry Maclean <hmac@github.com>
2022-06-28 08:50:54 -04:00
Asger F
a522562f93 Merge pull request #9369 from asgerf/python/api-graph-api
Python: API graph renaming and documentation
2022-06-28 14:48:12 +02:00
Arthur Baars
6e836c7eb8 Merge pull request #9706 from aibaars/update-tree-sitter-ruby-2
Ruby: update tree-sitter-ruby
2022-06-28 14:14:15 +02:00
Erik Krogh Kristensen
112caa3f5d rewrite qldoc based on review 2022-06-28 13:23:44 +02:00
yoff
834d2603a2 python: update use of barrier guard 2022-06-28 11:15:37 +00:00
Paolo Tranquilli
7f8bff571d Merge pull request #9729 from github/redsun82/swift-extraction
Swift: extract `ProtocolCompositionType` and all `BuiltinType`s
2022-06-28 12:30:47 +02:00
Paolo Tranquilli
131524d867 Swift: accept test changes
These are due to the changes on `toBeTested` that include canonical
types.
2022-06-28 12:16:08 +02:00
Asger F
b3b53360ae Python: change category to deprecated because library is apparently supported anymore 2022-06-28 12:14:28 +02:00
Asger F
5dfc3c6537 Python: rename change note again 2022-06-28 12:10:26 +02:00
Paolo Tranquilli
68a341d72c Swift: use createEntry in the whole type visitor 2022-06-28 12:06:19 +02:00
Paolo Tranquilli
57981384df Swift: extract ProtocolComposition- and BuiltinType 2022-06-28 12:01:36 +02:00
Paolo Tranquilli
b41cbaec33 Swift: add possibility to add flags in tests 2022-06-28 12:01:36 +02:00
Paolo Tranquilli
f2b589743a Swift: add possibility to collapse class hierarchy in tests 2022-06-28 12:01:36 +02:00
Asger F
d9f57e6d23 Python: rename change note file 2022-06-28 11:41:07 +02:00
Asger F
6d25fb6988 Python: add change note 2022-06-28 11:28:30 +02:00
Ian Lynagh
780f5abc67 Merge pull request #9724 from igfoo/igfoo/private
Kotlin: Make more methods private
2022-06-28 10:21:55 +01:00
Ian Lynagh
b6790ef735 Merge pull request #9725 from igfoo/igfoo/inline
Kotlin: Extract inlineability of functions
2022-06-28 10:21:30 +01:00
Tony Torralba
e0b4c63a53 Add new source kind to CsvValidation 2022-06-28 10:16:40 +02:00
Joe Farebrother
49b419c52e Update models to include manual tag 2022-06-28 10:10:28 +02:00
Joe Farebrother
55e78e3e25 Minor doc fixes + making directFileRead private 2022-06-28 10:10:28 +02:00
Joe Farebrother
a41f28ebe5 Use more file openning methods 2022-06-28 10:10:28 +02:00
Joe Farebrother
58fba20689 Add change note 2022-06-28 10:10:28 +02:00
Joe Farebrother
cb717a22bf Fix failing test cases 2022-06-28 10:10:27 +02:00
Joe Farebrother
810854d6b5 Add tests 2022-06-28 10:10:27 +02:00
Joe Farebrother
0e04f2b2e8 Add external storage souces 2022-06-28 10:10:27 +02:00
Asger F
4c73ab2679 Apply suggestions from code review
Co-authored-by: Taus <tausbn@github.com>
2022-06-28 09:48:53 +02:00
Asger F
a033338d20 Python: Explicitly mention lack of transitive flow in asSource/asSink 2022-06-28 09:46:26 +02:00
Asger F
9b27a7cbcd Python: Dont claim that external libraries are excluded from the database 2022-06-28 09:28:26 +02:00
Asger F
0346b6b67a Merge pull request #9698 from github/post-release-prep/codeql-cli-2.10.0
Post-release preparation for codeql-cli-2.10.0
2022-06-28 09:05:13 +02:00
yoff
67b6f215dc Apply suggestions from code review
Co-authored-by: Rasmus Wriedt Larsen <rasmuswriedtlarsen@gmail.com>
2022-06-28 08:05:53 +02:00
Brandon Stewart
4fb0264ec8 Merge branch 'main' into patch-1 2022-06-27 16:07:15 -04:00
Taus
dc0f50d49a Python: Clean up variable names
Makes it more consistent with the names used in
`legalMergeCandidateNonEmpty`.
2022-06-27 19:54:09 +00:00
Taus
8fc9ce9699 Python: Fix bad join in MRO
Fixes a bad join in `list_of_linearization_of_bases_plus_bases`.

Previvously, we joined together `ConsList` and `getBase` before filtering
these out using the recursive call. Now we do the recursion first.

Co-authored-by: yoff <yoff@github.com>
2022-06-27 19:54:09 +00:00
Robert Marsh
829fdd1ff6 C++: fix join order in UsingExpiredStackAddress 2022-06-27 15:28:14 -04:00
Andrew Eisenberg
43bb439b82 Add version info for running subset of queries 2022-06-27 12:03:23 -07:00
Ian Lynagh
3543864e0b Merge pull request #9723 from igfoo/igfoo/delegates
Kotlin: Mark DELEGATED_PROPERTY_ACCESSORs as compiler-generated
2022-06-27 19:48:53 +01:00
Asger F
cc57cb8af5 Merge branch 'main' into post-release-prep/codeql-cli-2.10.0 2022-06-27 20:37:25 +02:00
Ian Lynagh
44e69e1c09 Kotlin: Add Modifier.isInline() 2022-06-27 19:33:08 +01:00
Ian Lynagh
af672b4899 Kotlin: Add a changenote for Modifier.isInline() 2022-06-27 19:31:01 +01:00