Subsample sinks before scoring to avoid DCA timeouts

Locations only exist where there are locatable structures in the DB. Thus, select the largest location that contains the node and at most `neighborhoodSize` lines before and after the node.

.github/actions/cache-query-compilation/action.yml

@@ -23,19 +23,20 @@ runs:
       run: |
         MERGE_BASE=$(git cat-file commit $GITHUB_SHA | grep '^parent ' | head -1 | cut -f 2 -d " ")
         echo "merge_base=$MERGE_BASE" >> $GITHUB_ENV
-    - name: Restore cache (PR)
+    - name: Restore read-only cache (PR)
       if: ${{ github.event_name == 'pull_request' }}
-      uses: actions/cache/restore@v3
+      uses: erik-krogh/actions-cache@a88d0603fe5fb5606db9f002dfcadeb32b5f84c6
       with:
         path: '**/.cache'
+        read-only: true
         key: codeql-compile-${{ inputs.key }}-pr-${{ github.sha }}
         restore-keys: |
           codeql-compile-${{ inputs.key }}-${{ github.base_ref }}-${{ env.merge_base }}
           codeql-compile-${{ inputs.key }}-${{ github.base_ref }}-
           codeql-compile-${{ inputs.key }}-main-
-    - name: Fill cache (only branch push)
+    - name: Fill cache (push)
       if: ${{ github.event_name != 'pull_request' }}
-      uses: actions/cache@v3
+      uses: erik-krogh/actions-cache@a88d0603fe5fb5606db9f002dfcadeb32b5f84c6
       with:
         path: '**/.cache'
         key: codeql-compile-${{ inputs.key }}-${{ github.ref_name }}-${{ github.sha }} # just fill on main

.github/actions/fetch-codeql/action.yml

@@ -19,6 +19,4 @@ runs:
         gh extension install github/gh-codeql
         gh codeql set-channel "$CHANNEL"
         gh codeql version
-        printf "CODEQL_FETCHED_CODEQL_PATH=" >> "${GITHUB_ENV}"
-        gh codeql version --format=json | jq -r .unpackedLocation >> "${GITHUB_ENV}"
         gh codeql version --format=json | jq -r .unpackedLocation >> "${GITHUB_PATH}"

.github/actions/find-latest-bundle/action.yml

@@ -0,0 +1,26 @@
+name: Find Latest CodeQL Bundle
+description: Finds the URL of the latest released version of the CodeQL bundle.
+outputs:
+  url:
+    description: The download URL of the latest CodeQL bundle release
+    value: ${{ steps.find-latest.outputs.url }}
+runs:
+  using: composite
+  steps:
+    - name: Find Latest Release
+      id: find-latest
+      shell: pwsh
+      run: |
+        $Latest = gh release list --repo github/codeql-action --exclude-drafts --limit 1000 |
+          ForEach-Object { $C = $_ -split "`t"; return @{ type = $C[1]; tag = $C[2]; } } |
+          Where-Object { $_.type -eq 'Latest' }
+
+        $Tag = $Latest.tag
+        if ($Tag -eq '') {
+          throw 'Failed to find latest bundle release.'
+        }
+
+        Write-Output "Latest bundle tag is '${Tag}'."
+        "url=https://github.com/github/codeql-action/releases/download/${Tag}/codeql-bundle-linux64.tar.gz" >> $env:GITHUB_OUTPUT
+      env:
+        GITHUB_TOKEN: ${{ github.token }}

.github/actions/os-version/action.yml

@@ -1,32 +0,0 @@
-name: OS Version
-description: Get OS version.
-
-outputs:
-  version:
-    description: "OS version"
-    value: ${{ steps.version.outputs.version }}
-
-runs:
-  using: composite
-  steps:
-    - if: runner.os == 'Linux'
-      shell: bash
-      run: |
-        . /etc/os-release
-        echo "VERSION=${NAME} ${VERSION}" >> $GITHUB_ENV
-    - if: runner.os == 'Windows'
-      shell: powershell
-      run: |
-        $objects = systeminfo.exe /FO CSV | ConvertFrom-Csv
-        "VERSION=$($objects.'OS Name') $($objects.'OS Version')" >> $env:GITHUB_ENV
-    - if: runner.os == 'macOS'
-      shell: bash
-      run: |
-        echo "VERSION=$(sw_vers -productName) $(sw_vers -productVersion)" >> $GITHUB_ENV
-    - name: Emit OS version
-      id: version
-      shell: bash
-      run: |
-        echo "$VERSION"
-        echo "version=${VERSION}" >> $GITHUB_OUTPUT
-

.github/dependabot.yml

@@ -1,12 +1,19 @@
 version: 2
 updates:
   - package-ecosystem: "cargo"
-    directory: "ruby"
+    directory: "ruby/node-types"
     schedule:
       interval: "daily"
-
   - package-ecosystem: "cargo"
-    directory: "ql"
+    directory: "ruby/generator"
+    schedule:
+      interval: "daily"
+  - package-ecosystem: "cargo"
+    directory: "ruby/extractor"
+    schedule:
+      interval: "daily"
+  - package-ecosystem: "cargo"
+    directory: "ruby/autobuilder"
     schedule:
       interval: "daily"
 

.github/workflows/atm-check-query-suite.yml

@@ -13,7 +13,7 @@ on:
 
 jobs:
   atm-check-query-suite:
-    runs-on: ubuntu-latest-xl
+    runs-on: ubuntu-latest
 
     steps:
       - uses: actions/checkout@v3
@@ -23,12 +23,6 @@ jobs:
         with:
           channel: release
 
-      - name: Cache compilation cache
-        id: query-cache
-        uses: ./.github/actions/cache-query-compilation
-        with: 
-          key: atm-suite
-
       - name: Install ATM model
         run: |
           set -exu
@@ -56,13 +50,10 @@ jobs:
           echo "SARIF_PATH=${SARIF_PATH}" >> "${GITHUB_ENV}"
 
           codeql database analyze \
-            --threads=0 \
-            --ram 50000 \
             --format sarif-latest \
             --output "${SARIF_PATH}" \
             --sarif-group-rules-by-pack \
             -vv \
-            --compilation-cache "${{ steps.query-cache.outputs.cache-dir }}" \
             -- \
             "${DB_PATH}" \
             "${QUERY_PACK}/${QUERY_SUITE}"

.github/workflows/check-change-note.yml

@@ -26,9 +26,3 @@ jobs:
         run: |
           gh api 'repos/${{github.repository}}/pulls/${{github.event.number}}/files' --paginate --jq 'any(.[].filename ; test("/change-notes/.*[.]md$"))' |
           grep true -c
-      - name: Fail if the change note filename doesn't match the expected format. The file name must be of the form 'YYYY-MM-DD.md' or 'YYYY-MM-DD-{title}.md', where '{title}' is arbitrary text.
-        env:
-          GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
-        run: |
-          gh api 'repos/${{github.repository}}/pulls/${{github.event.number}}/files' --paginate --jq '[.[].filename | select(test("/change-notes/.*[.]md$"))] | all(test("/change-notes/[0-9]{4}-[0-9]{2}-[0-9]{2}.*[.]md$"))' |
-          grep true -c

.github/workflows/check-query-ids.yml

@@ -1,21 +0,0 @@
-name: Check query IDs
-
-on:
-  pull_request:
-    paths:
-      - "**/src/**/*.ql"
-      - misc/scripts/check-query-ids.py
-      - .github/workflows/check-query-ids.yml
-    branches:
-      - main
-      - "rc/*"
-  workflow_dispatch:
-
-jobs:
-  check:
-    name: Check query IDs
-    runs-on: ubuntu-latest
-    steps:
-      - uses: actions/checkout@v3
-      - name: Check for duplicate query IDs
-        run: python3 misc/scripts/check-query-ids.py

.github/workflows/close-stale.yml

@@ -12,7 +12,7 @@ jobs:
     runs-on: ubuntu-latest
 
     steps:
-    - uses: actions/stale@v7
+    - uses: actions/stale@v6
       with:
         repo-token: ${{ secrets.GITHUB_TOKEN }}
         stale-issue-message: 'This issue is stale because it has been open 14 days with no activity. Comment or remove the `Stale` label in order to avoid having this issue closed in 7 days.'

.github/workflows/codeql-analysis.yml

@@ -28,9 +28,9 @@ jobs:
 
     steps:
     - name: Setup dotnet
-      uses: actions/setup-dotnet@v3
+      uses: actions/setup-dotnet@v2
       with:
-        dotnet-version: 7.0.102
+        dotnet-version: 6.0.202
 
     - name: Checkout repository
       uses: actions/checkout@v3

.github/workflows/csharp-qltest.yml

@@ -77,10 +77,10 @@ jobs:
       - name: Setup dotnet
         uses: actions/setup-dotnet@v3
         with:
-          dotnet-version: 7.0.102
+          dotnet-version: 6.0.202
       - name: Extractor unit tests
         run: |
-          dotnet test -p:RuntimeFrameworkVersion=7.0.2 "${{ github.workspace }}/csharp/extractor/Semmle.Util.Tests"
-          dotnet test -p:RuntimeFrameworkVersion=7.0.2 "${{ github.workspace }}/csharp/extractor/Semmle.Extraction.Tests"
-          dotnet test -p:RuntimeFrameworkVersion=7.0.2 "${{ github.workspace }}/csharp/autobuilder/Semmle.Autobuild.CSharp.Tests"
-          dotnet test -p:RuntimeFrameworkVersion=7.0.2 "${{ github.workspace }}/cpp/autobuilder/Semmle.Autobuild.Cpp.Tests"
+          dotnet test -p:RuntimeFrameworkVersion=6.0.4 "${{ github.workspace }}/csharp/extractor/Semmle.Util.Tests"
+          dotnet test -p:RuntimeFrameworkVersion=6.0.4 "${{ github.workspace }}/csharp/extractor/Semmle.Extraction.Tests"
+          dotnet test -p:RuntimeFrameworkVersion=6.0.4 "${{ github.workspace }}/csharp/autobuilder/Semmle.Autobuild.CSharp.Tests"
+          dotnet test -p:RuntimeFrameworkVersion=6.0.4 "${{ github.workspace }}/cpp/autobuilder/Semmle.Autobuild.Cpp.Tests"

.github/workflows/go-tests-other-os.yml

@@ -12,10 +12,10 @@ jobs:
     name: Test MacOS
     runs-on: macos-latest
     steps:
-      - name: Set up Go 1.20
+      - name: Set up Go 1.19
         uses: actions/setup-go@v3
         with:
-          go-version: 1.20.0
+          go-version: 1.19
         id: go
 
       - name: Check out code
@@ -47,10 +47,10 @@ jobs:
     name: Test Windows
     runs-on: windows-latest-xl
     steps:
-      - name: Set up Go 1.20
+      - name: Set up Go 1.19
         uses: actions/setup-go@v3
         with:
-          go-version: 1.20.0
+          go-version: 1.19
         id: go
 
       - name: Check out code

.github/workflows/go-tests.yml

@@ -20,10 +20,10 @@ jobs:
     name: Test Linux (Ubuntu)
     runs-on: ubuntu-latest-xl
     steps:
-      - name: Set up Go 1.20
+      - name: Set up Go 1.19
         uses: actions/setup-go@v3
         with:
-          go-version: 1.20.0
+          go-version: 1.19
         id: go
 
       - name: Check out code

.github/workflows/mad_modelDiff.yml

@@ -11,7 +11,7 @@ on:
     branches:
       - main
     paths:
-      - "java/ql/src/utils/modelgenerator/**/*.*"
+      - "java/ql/src/utils/model-generator/**/*.*"
       - ".github/workflows/mad_modelDiff.yml"
 
 permissions:
@@ -40,12 +40,12 @@ jobs:
       - name: Download database
         env:
           SLUG: ${{ matrix.slug }}
-          GH_TOKEN: ${{ github.token }}
         run: |
           set -x
           mkdir lib-dbs
           SHORTNAME=${SLUG//[^a-zA-Z0-9_]/}
-          gh api -H "Accept: application/zip" "/repos/${SLUG}/code-scanning/codeql/databases/java" > "$SHORTNAME.zip"
+          projectId=`curl -s https://lgtm.com/api/v1.0/projects/g/${SLUG} | jq .id`
+          curl -L "https://lgtm.com/api/v1.0/snapshots/$projectId/java" -o "$SHORTNAME.zip"
           unzip -q -d "${SHORTNAME}-db" "${SHORTNAME}.zip"
           mkdir "lib-dbs/$SHORTNAME/"
           mv "${SHORTNAME}-db/"$(ls -1 "${SHORTNAME}"-db)/* "lib-dbs/${SHORTNAME}/"
@@ -61,7 +61,7 @@ jobs:
             DATABASE=$2
             cd codeql-$QL_VARIANT
             SHORTNAME=`basename $DATABASE`
-            python java/ql/src/utils/modelgenerator/GenerateFlowModel.py --with-summaries --with-sinks $DATABASE ${SHORTNAME}.temp.model.yml
+            python java/ql/src/utils/model-generator/GenerateFlowModel.py --with-summaries --with-sinks $DATABASE ${SHORTNAME}.temp.model.yml
             mv java/ql/lib/ext/generated/${SHORTNAME}.temp.model.yml $MODELS/${SHORTNAME}Generated_${QL_VARIANT}.model.yml
             cd ..
           }
@@ -100,6 +100,4 @@ jobs:
         with:
           name: diffs
           path: tmp-models/*.html
-          # An html file is only produced if the generated models differ.
-          if-no-files-found: ignore
           retention-days: 20

.github/workflows/mad_regenerate-models.yml

@@ -50,7 +50,7 @@ jobs:
           SLUG: ${{ matrix.slug }}
         run: |
           SHORTNAME=${SLUG//[^a-zA-Z0-9_]/}
-          java/ql/src/utils/modelgenerator/RegenerateModels.py "${SLUG}" dbs/${SHORTNAME}
+          java/ql/src/utils/model-generator/RegenerateModels.py "${SLUG}" dbs/${SHORTNAME}
       - name: Stage changes
         run: |
           find java -name "*.model.yml" -print0 | xargs -0 git add

.github/workflows/ql-for-ql-build.yml

@@ -22,54 +22,142 @@ jobs:
     steps:
       ### Build the queries ###
       - uses: actions/checkout@v3
+      - name: Find latest bundle
+        id: find-latest-bundle
+        uses: ./.github/actions/find-latest-bundle
       - name: Find codeql
         id: find-codeql
-        uses: github/codeql-action/init@v2
+        uses: github/codeql-action/init@77a8d2d10c0b403a8b4aadbd223dc489ecd22683
         with:
           languages: javascript # does not matter
-      - uses: ./.github/actions/os-version
-        id: os_version
+          tools: ${{ steps.find-latest-bundle.outputs.url }}
+      - name: Get CodeQL version
+        id: get-codeql-version
+        run: |
+          echo "version=$("${CODEQL}" --version | head -n 1 | rev | cut -d " " -f 1 | rev)" >> $GITHUB_OUTPUT
+        shell: bash
+        env:
+          CODEQL: ${{ steps.find-codeql.outputs.codeql-path }}
+      - name: Cache entire pack
+        id: cache-pack
+        uses: actions/cache@v3
+        with:
+          path: ${{ runner.temp }}/pack
+          key: ${{ runner.os }}-pack-${{ hashFiles('ql/**/Cargo.lock') }}-${{ hashFiles('ql/**/*.rs') }}-${{ hashFiles('ql/**/*.ql*') }}-${{ hashFiles('ql/**/qlpack.yml') }}-${{ hashFiles('ql/ql/src/ql.dbscheme*') }}-${{ steps.get-codeql-version.outputs.version }}--${{ hashFiles('.github/workflows/ql-for-ql-build.yml') }}
+      - name: Cache queries
+        if: steps.cache-pack.outputs.cache-hit != 'true'
+        id: cache-queries
+        uses: actions/cache@v3
+        with:
+          path: ${{ runner.temp }}/queries
+          key: queries-${{ hashFiles('ql/**/*.ql*') }}-${{ hashFiles('ql/**/qlpack.yml') }}-${{ hashFiles('ql/ql/src/ql.dbscheme*') }}-${{ steps.get-codeql-version.outputs.version }}--${{ hashFiles('.github/workflows/ql-for-ql-build.yml') }}
+      - name: Build query pack
+        if: steps.cache-queries.outputs.cache-hit != 'true' && steps.cache-pack.outputs.cache-hit != 'true'
+        run: |
+          cd ql/ql/src
+          "${CODEQL}" pack create -j 16
+          mv .codeql/pack/codeql/ql/0.0.0 ${{ runner.temp }}/queries
+        env:
+          CODEQL: ${{ steps.find-codeql.outputs.codeql-path }}
+      - name: Move cache queries to pack
+        if: steps.cache-pack.outputs.cache-hit != 'true'
+        run: |
+          cp -r ${{ runner.temp }}/queries ${{ runner.temp }}/pack
+        env:
+          CODEQL: ${{ steps.find-codeql.outputs.codeql-path }}
+
       ### Build the extractor ###
       - name: Cache entire extractor
+        if: steps.cache-pack.outputs.cache-hit != 'true'
         id: cache-extractor
         uses: actions/cache@v3
         with:
-          path: ql/extractor-pack/
-          key: ${{ runner.os }}-${{ steps.os_version.outputs.version }}-extractor-${{ hashFiles('ql/**/Cargo.lock') }}-${{ hashFiles('ql/**/*.rs') }}
+          path: |
+            ql/target/release/ql-autobuilder
+            ql/target/release/ql-autobuilder.exe
+            ql/target/release/ql-extractor
+            ql/target/release/ql-extractor.exe
+          key: ${{ runner.os }}-extractor-${{ hashFiles('ql/**/Cargo.lock') }}-${{ hashFiles('ql/**/*.rs') }}
       - name: Cache cargo
-        if: steps.cache-extractor.outputs.cache-hit != 'true'
+        if: steps.cache-extractor.outputs.cache-hit != 'true' && steps.cache-pack.outputs.cache-hit != 'true'
         uses: actions/cache@v3
         with:
           path: |
             ~/.cargo/registry
             ~/.cargo/git
             ql/target
-          key: ${{ runner.os }}-${{ steps.os_version.outputs.version }}-rust-cargo-${{ hashFiles('ql/**/Cargo.lock') }}
+          key: ${{ runner.os }}-rust-cargo-${{ hashFiles('ql/**/Cargo.lock') }}
+      - name: Check formatting
+        if: steps.cache-extractor.outputs.cache-hit != 'true' && steps.cache-pack.outputs.cache-hit != 'true'
+        run: cd ql; cargo fmt --all -- --check
+      - name: Build
+        if: steps.cache-extractor.outputs.cache-hit != 'true' && steps.cache-pack.outputs.cache-hit != 'true'
+        run: cd ql; cargo build --verbose
+      - name: Run tests
+        if: steps.cache-extractor.outputs.cache-hit != 'true' && steps.cache-pack.outputs.cache-hit != 'true'
+        run: cd ql; cargo test --verbose
       - name: Release build
-        if: steps.cache-extractor.outputs.cache-hit != 'true'
-        run: cd ql; ./scripts/create-extractor-pack.sh       
-        env:
-          GH_TOKEN: ${{ github.token }}   
-      - name: Cache compilation cache
-        id: query-cache
-        uses: ./.github/actions/cache-query-compilation
-        with: 
-          key: run-ql-for-ql
-      - name: Make database and analyze
+        if: steps.cache-extractor.outputs.cache-hit != 'true' && steps.cache-pack.outputs.cache-hit != 'true'
+        run: cd ql; cargo build --release
+      - name: Generate dbscheme
+        if: steps.cache-extractor.outputs.cache-hit != 'true' && steps.cache-pack.outputs.cache-hit != 'true'
+        run: ql/target/release/ql-generator --dbscheme ql/ql/src/ql.dbscheme --library ql/ql/src/codeql_ql/ast/internal/TreeSitter.qll
+
+      ### Package the queries and extractor ###
+      - name: Package pack
+        if: steps.cache-pack.outputs.cache-hit != 'true'
         run: |
-          ${CODEQL} database create -l=ql --search-path ql/extractor-pack ${DB}
-          ${CODEQL} database analyze -j0 --format=sarif-latest --output=ql-for-ql.sarif ${DB} ql/ql/src/codeql-suites/ql-code-scanning.qls  --compilation-cache "${{ steps.query-cache.outputs.cache-dir }}"
-        env: 
-          CODEQL: ${{ steps.find-codeql.outputs.codeql-path }}
-          DB: ${{ runner.temp }}/DB
-          LGTM_INDEX_FILTERS: |
-            exclude:ql/ql/test
-            exclude:*/ql/lib/upgrades/
-      - name: Upload sarif to code-scanning
-        uses: github/codeql-action/upload-sarif@v2
+          cp -r ql/codeql-extractor.yml ql/tools ql/ql/src/ql.dbscheme.stats ${PACK}/
+          mkdir -p ${PACK}/tools/linux64
+          cp ql/target/release/ql-autobuilder  ${PACK}/tools/linux64/autobuilder
+          cp ql/target/release/ql-extractor ${PACK}/tools/linux64/extractor
+          chmod +x ${PACK}/tools/linux64/autobuilder
+          chmod +x ${PACK}/tools/linux64/extractor
+        env:
+          PACK: ${{ runner.temp }}/pack
+
+      ### Run the analysis ###
+      - name: Hack codeql-action options
+        run: |
+          JSON=$(jq -nc --arg pack "${PACK}" '.database."run-queries"=["--search-path", $pack] | .resolve.queries=["--search-path", $pack] | .resolve.extractor=["--search-path", $pack] | .resolve.languages=["--search-path", $pack] | .database.init=["--search-path", $pack]')
+          echo "CODEQL_ACTION_EXTRA_OPTIONS=${JSON}" >> ${GITHUB_ENV}
+        env:
+          PACK: ${{ runner.temp }}/pack
+
+      - name: Create CodeQL config file
+        run: |
+          echo "paths-ignore:" >> ${CONF}
+          echo "  - ql/ql/test" >> ${CONF}
+          echo "  - \"*/ql/lib/upgrades/\"" >> ${CONF}
+          echo "disable-default-queries: true" >> ${CONF}
+          echo "queries:" >> ${CONF}
+          echo "  - uses: ./ql/ql/src/codeql-suites/ql-code-scanning.qls" >> ${CONF}
+          echo "Config file: "
+          cat ${CONF}
+        env:
+          CONF: ./ql-for-ql-config.yml
+      - name: Initialize CodeQL
+        uses: github/codeql-action/init@77a8d2d10c0b403a8b4aadbd223dc489ecd22683
         with:
-          sarif_file: ql-for-ql.sarif
-          category: ql-for-ql
+          languages: ql
+          db-location: ${{ runner.temp }}/db
+          config-file: ./ql-for-ql-config.yml
+          tools: ${{ steps.find-latest-bundle.outputs.url }}
+      - name: Move pack cache
+        run: |
+          cp -r ${PACK}/.cache ql/ql/src/.cache
+        env:
+          PACK: ${{ runner.temp }}/pack
+
+      - name: Perform CodeQL Analysis
+        uses: github/codeql-action/analyze@77a8d2d10c0b403a8b4aadbd223dc489ecd22683
+        with:
+          category: "ql-for-ql"
+      - name: Copy sarif file to CWD
+        run: cp ../results/ql.sarif ./ql-for-ql.sarif
+      - name: Fixup the $scema in sarif  # Until https://github.com/microsoft/sarif-vscode-extension/pull/436/ is part in a stable release
+        run: |
+          sed -i 's/\$schema.*/\$schema": "https:\/\/raw.githubusercontent.com\/oasis-tcs\/sarif-spec\/master\/Schemata\/sarif-schema-2.1.0",/' ql-for-ql.sarif
       - name: Sarif as artifact
         uses: actions/upload-artifact@v3
         with:
@@ -84,4 +172,4 @@ jobs:
         with:
           name: ql-for-ql-langs
           path: split-sarif
-          retention-days: 1
+          retention-days: 1

.github/workflows/ql-for-ql-dataset_measure.yml

@@ -25,18 +25,16 @@ jobs:
 
       - name: Find codeql
         id: find-codeql
-        uses: github/codeql-action/init@v2
+        uses: github/codeql-action/init@77a8d2d10c0b403a8b4aadbd223dc489ecd22683
         with:
           languages: javascript # does not matter
-      - uses: ./.github/actions/os-version
-        id: os_version
       - uses: actions/cache@v3
         with:
           path: |
             ~/.cargo/registry
             ~/.cargo/git
             ql/target
-          key: ${{ runner.os }}-${{ steps.os_version.outputs.version }}-qltest-cargo-${{ hashFiles('ql/**/Cargo.lock') }}
+          key: ${{ runner.os }}-qltest-cargo-${{ hashFiles('ql/**/Cargo.lock') }}
       - name: Build Extractor
         run: cd ql; env "PATH=$PATH:`dirname ${CODEQL}`" ./scripts/create-extractor-pack.sh
         env:

.github/workflows/ql-for-ql-tests.yml

@@ -6,13 +6,11 @@ on:
     paths:
       - "ql/**"
       - codeql-workspace.yml
-      - .github/workflows/ql-for-ql-tests.yml
   pull_request:
     branches: [main]
     paths:
       - "ql/**"
       - codeql-workspace.yml
-      - .github/workflows/ql-for-ql-tests.yml
 
 env:
   CARGO_TERM_COLOR: always
@@ -24,86 +22,28 @@ jobs:
       - uses: actions/checkout@v3
       - name: Find codeql
         id: find-codeql
-        uses: github/codeql-action/init@v2
+        uses: github/codeql-action/init@77a8d2d10c0b403a8b4aadbd223dc489ecd22683
         with:
           languages: javascript # does not matter
-      - uses: ./.github/actions/os-version
-        id: os_version
       - uses: actions/cache@v3
         with:
           path: |
             ~/.cargo/registry
             ~/.cargo/git
             ql/target
-          key: ${{ runner.os }}-${{ steps.os_version.outputs.version }}-qltest-cargo-${{ hashFiles('ql/rust-toolchain.toml', 'ql/**/Cargo.lock') }}
-      - name: Check formatting
-        run: cd ql; cargo fmt --all -- --check
+          key: ${{ runner.os }}-qltest-cargo-${{ hashFiles('ql/**/Cargo.lock') }}
       - name: Build extractor
         run: |
           cd ql;
           codeqlpath=$(dirname ${{ steps.find-codeql.outputs.codeql-path }});
           env "PATH=$PATH:$codeqlpath" ./scripts/create-extractor-pack.sh
-      - name: Cache compilation cache
-        id: query-cache
-        uses: ./.github/actions/cache-query-compilation
-        with: 
-          key: ql-for-ql-tests
       - name: Run QL tests
         run: |
-          "${CODEQL}" test run --check-databases --check-unused-labels --check-repeated-labels --check-redefined-labels --check-use-before-definition --search-path "${{ github.workspace }}/ql/extractor-pack" --consistency-queries ql/ql/consistency-queries --compilation-cache "${{ steps.query-cache.outputs.cache-dir }}" ql/ql/test
+          "${CODEQL}" test run --check-databases --check-unused-labels --check-repeated-labels --check-redefined-labels --check-use-before-definition --search-path "${{ github.workspace }}/ql/extractor-pack" --consistency-queries ql/ql/consistency-queries ql/ql/test
         env:
           CODEQL: ${{ steps.find-codeql.outputs.codeql-path }}
-
-  other-os: 
-    strategy:
-      matrix:
-        os: [macos-latest, windows-latest]
-    needs: [qltest]
-    runs-on: ${{ matrix.os }}
-    steps:
-      - uses: actions/checkout@v3
-      - name: Install GNU tar 
-        if: runner.os == 'macOS'
+      - name: Check QL formatting
         run: |
-          brew install gnu-tar
-          echo "/usr/local/opt/gnu-tar/libexec/gnubin" >> $GITHUB_PATH
-      - name: Find codeql
-        id: find-codeql
-        uses: github/codeql-action/init@v2
-        with:
-          languages: javascript # does not matter
-      - uses: ./.github/actions/os-version
-        id: os_version
-      - uses: actions/cache@v3
-        with:
-          path: |
-            ~/.cargo/registry
-            ~/.cargo/git
-            ql/target
-          key: ${{ runner.os }}-${{ steps.os_version.outputs.version }}-qltest-cargo-${{ hashFiles('ql/rust-toolchain.toml', 'ql/**/Cargo.lock') }}
-      - name: Build extractor
-        if: runner.os != 'Windows'
-        run: |
-          cd ql;
-          codeqlpath=$(dirname ${{ steps.find-codeql.outputs.codeql-path }});
-          env "PATH=$PATH:$codeqlpath" ./scripts/create-extractor-pack.sh
-      - name: Build extractor (Windows)
-        if: runner.os == 'Windows'
-        shell: pwsh
-        run: |
-          cd ql;
-          $Env:PATH += ";$(dirname ${{ steps.find-codeql.outputs.codeql-path }})"
-          pwsh ./scripts/create-extractor-pack.ps1
-      - name: Run a single QL tests - Unix
-        if: runner.os != 'Windows'
-        run: |
-          "${CODEQL}" test run --check-databases --search-path "${{ github.workspace }}/ql/extractor-pack" ql/ql/test/queries/style/DeadCode/DeadCode.qlref
+          find ql/ql/src "(" -name "*.ql" -or -name "*.qll" ")" -print0 | xargs -0 "${CODEQL}" query format --check-only
         env:
           CODEQL: ${{ steps.find-codeql.outputs.codeql-path }}
-      - name: Run a single QL tests - Windows
-        if: runner.os == 'Windows'
-        shell: pwsh
-        run: |
-          $Env:PATH += ";$(dirname ${{ steps.find-codeql.outputs.codeql-path }})"
-          codeql test run --check-databases --search-path "${{ github.workspace }}/ql/extractor-pack" ql/ql/test/queries/style/DeadCode/DeadCode.qlref
-      

.github/workflows/ruby-build.yml

@@ -48,8 +48,6 @@ jobs:
         run: |
           brew install gnu-tar
           echo "/usr/local/opt/gnu-tar/libexec/gnubin" >> $GITHUB_PATH
-      - uses: ./.github/actions/os-version
-        id: os_version
       - name: Cache entire extractor
         uses: actions/cache@v3
         id: cache-extractor
@@ -60,7 +58,7 @@ jobs:
             ruby/target/release/ruby-extractor
             ruby/target/release/ruby-extractor.exe
             ruby/ql/lib/codeql/ruby/ast/internal/TreeSitter.qll
-          key: ${{ runner.os }}-${{ steps.os_version.outputs.version }}-ruby-extractor-${{ hashFiles('ruby/rust-toolchain.toml', 'ruby/**/Cargo.lock') }}--${{ hashFiles('ruby/**/*.rs') }}
+          key: ${{ runner.os }}-ruby-extractor-${{ hashFiles('ruby/rust-toolchain.toml', 'ruby/**/Cargo.lock') }}--${{ hashFiles('ruby/**/*.rs') }}
       - uses: actions/cache@v3
         if: steps.cache-extractor.outputs.cache-hit != 'true'
         with:
@@ -68,7 +66,7 @@ jobs:
             ~/.cargo/registry
             ~/.cargo/git
             ruby/target
-          key: ${{ runner.os }}-${{ steps.os_version.outputs.version }}-ruby-rust-cargo-${{ hashFiles('ruby/rust-toolchain.toml', 'ruby/**/Cargo.lock') }}
+          key: ${{ runner.os }}-ruby-rust-cargo-${{ hashFiles('ruby/rust-toolchain.toml', 'ruby/**/Cargo.lock') }}
       - name: Check formatting
         if: steps.cache-extractor.outputs.cache-hit != 'true'
         run: cargo fmt --all -- --check
@@ -117,10 +115,9 @@ jobs:
       - name: Build Query Pack
         run: |
           rm -rf target/packs
+          codeql pack create ../shared/ssa --output target/packs
           codeql pack create ../misc/suite-helpers --output target/packs
           codeql pack create ../shared/regex --output target/packs
-          codeql pack create ../shared/ssa --output target/packs
-          codeql pack create ../shared/tutorial --output target/packs
           codeql pack create ql/lib --output target/packs
           codeql pack create -j0 ql/src --output target/packs --compilation-cache "${{ steps.query-cache.outputs.cache-dir }}"
           PACK_FOLDER=$(readlink -f target/packs/codeql/ruby-queries/*)
@@ -205,6 +202,11 @@ jobs:
       - name: Fetch CodeQL
         uses: ./.github/actions/fetch-codeql
 
+      - uses: actions/checkout@v3
+        with:
+          repository: Shopify/example-ruby-app
+          ref: 67a0decc5eb550f3a9228eda53925c3afd40dfe9
+
       - name: Download Ruby bundle
         uses: actions/download-artifact@v3
         with:
@@ -213,15 +215,26 @@ jobs:
       - name: Unzip Ruby bundle
         shell: bash
         run: unzip -q -d "${{ runner.temp }}/ruby-bundle" "${{ runner.temp }}/codeql-ruby-bundle.zip"
-
+      - name: Prepare test files
+        shell: bash
+        run: |
+          echo "import codeql.ruby.AST select count(File f)" > "test.ql"
+          echo "| 4 |" > "test.expected"
+          echo 'name: sample-tests
+          version: 0.0.0
+          dependencies:
+            codeql/ruby-all: "*"
+          extractor: ruby
+          tests: .
+          ' > qlpack.yml
       - name: Run QL test
         shell: bash
         run: |
-          codeql test run --search-path "${{ runner.temp }}/ruby-bundle" --additional-packs "${{ runner.temp }}/ruby-bundle" ruby/ql/test/library-tests/ast/constants/
+          codeql test run --search-path "${{ runner.temp }}/ruby-bundle" --additional-packs "${{ runner.temp }}/ruby-bundle" .
       - name: Create database
         shell: bash
         run: |
-          codeql database create --search-path "${{ runner.temp }}/ruby-bundle" --language ruby --source-root ruby/ql/test/library-tests/ast/constants/ ../database
+          codeql database create --search-path "${{ runner.temp }}/ruby-bundle" --language ruby --source-root . ../database
       - name: Analyze database
         shell: bash
         run: |

.github/workflows/swift.yml

@@ -65,7 +65,6 @@ jobs:
     if : ${{ github.event_name == 'pull_request' }}
     needs: build-and-test-macos
     runs-on: macos-12-xl
-    timeout-minutes: 60
     steps:
       - uses: actions/checkout@v3
       - uses: ./swift/actions/run-integration-tests

CONTRIBUTING.md

@@ -25,7 +25,6 @@ If you have an idea for a query that you would like to share with other CodeQL u
 
     Each language-specific directory contains further subdirectories that group queries based on their `@tags` or purpose.
     - Experimental queries and libraries are stored in the `experimental` subdirectory within each language-specific directory in the [CodeQL repository](https://github.com/github/codeql). For example, experimental Java queries and libraries are stored in `java/ql/src/experimental` and any corresponding tests in `java/ql/test/experimental`.
-    - Experimental queries need to include `experimental` in their `@tags`
     - The structure of an `experimental` subdirectory mirrors the structure of its parent directory.
     - Select or create an appropriate directory in `experimental` based on the existing directory structure of `experimental` or its parent directory.
 

README.md

@@ -10,8 +10,6 @@ There is [extensive documentation](https://codeql.github.com/docs/) on getting s
 
 We welcome contributions to our standard library and standard checks. Do you have an idea for a new check, or how to improve an existing query? Then please go ahead and open a pull request! Before you do, though, please take the time to read our [contributing guidelines](CONTRIBUTING.md). You can also consult our [style guides](https://github.com/github/codeql/tree/main/docs) to learn how to format your code for consistency and clarity, how to write query metadata, and how to write query help documentation for your query.
 
-For information on contributing to CodeQL documentation, see the "[contributing guide](docs/codeql/CONTRIBUTING.md)" for docs.
-
 ## License
 
 The code in this repository is licensed under the [MIT License](LICENSE) by [GitHub](https://github.com).

config/identical-files.json

@@ -29,14 +29,13 @@
     "csharp/ql/lib/semmle/code/csharp/dataflow/internal/DataFlowImplForContentDataFlow.qll",
     "go/ql/lib/semmle/go/dataflow/internal/DataFlowImpl.qll",
     "go/ql/lib/semmle/go/dataflow/internal/DataFlowImpl2.qll",
-    "go/ql/lib/semmle/go/dataflow/internal/DataFlowImplForStringsNewReplacer.qll",
     "python/ql/lib/semmle/python/dataflow/new/internal/DataFlowImpl.qll",
     "python/ql/lib/semmle/python/dataflow/new/internal/DataFlowImpl2.qll",
     "python/ql/lib/semmle/python/dataflow/new/internal/DataFlowImpl3.qll",
     "python/ql/lib/semmle/python/dataflow/new/internal/DataFlowImpl4.qll",
-    "python/ql/lib/semmle/python/dataflow/new/internal/DataFlowImplForRegExp.qll",
     "ruby/ql/lib/codeql/ruby/dataflow/internal/DataFlowImpl.qll",
     "ruby/ql/lib/codeql/ruby/dataflow/internal/DataFlowImpl2.qll",
+    "ruby/ql/lib/codeql/ruby/dataflow/internal/DataFlowImplForRegExp.qll",
     "ruby/ql/lib/codeql/ruby/dataflow/internal/DataFlowImplForHttpClientLibraries.qll",
     "ruby/ql/lib/codeql/ruby/dataflow/internal/DataFlowImplForPathname.qll",
     "swift/ql/lib/codeql/swift/dataflow/internal/DataFlowImpl.qll"
@@ -403,6 +402,16 @@
     "csharp/ql/lib/semmle/code/csharp/dataflow/internal/ControlFlowReachability.qll",
     "csharp/ql/lib/semmle/code/csharp/dataflow/internal/rangeanalysis/ControlFlowReachability.qll"
   ],
+  "Inline Test Expectations": [
+    "cpp/ql/test/TestUtilities/InlineExpectationsTest.qll",
+    "csharp/ql/test/TestUtilities/InlineExpectationsTest.qll",
+    "java/ql/test/TestUtilities/InlineExpectationsTest.qll",
+    "python/ql/test/TestUtilities/InlineExpectationsTest.qll",
+    "ruby/ql/test/TestUtilities/InlineExpectationsTest.qll",
+    "ql/ql/test/TestUtilities/InlineExpectationsTest.qll",
+    "go/ql/test/TestUtilities/InlineExpectationsTest.qll",
+    "swift/ql/test/TestUtilities/InlineExpectationsTest.qll"
+  ],
   "C++ ExternalAPIs": [
     "cpp/ql/src/Security/CWE/CWE-020/ExternalAPIs.qll",
     "cpp/ql/src/Security/CWE/CWE-020/ir/ExternalAPIs.qll"
@@ -461,10 +470,6 @@
     "javascript/ql/src/Comments/CommentedOutCodeReferences.inc.qhelp",
     "python/ql/src/Lexical/CommentedOutCodeReferences.inc.qhelp"
   ],
-  "ThreadResourceAbuse qhelp": [
-    "java/ql/src/experimental/Security/CWE/CWE-400/LocalThreadResourceAbuse.qhelp",
-    "java/ql/src/experimental/Security/CWE/CWE-400/ThreadResourceAbuse.qhelp"
-  ],
   "IDE Contextual Queries": [
     "cpp/ql/lib/IDEContextual.qll",
     "csharp/ql/lib/IDEContextual.qll",
@@ -496,6 +501,14 @@
     "python/ql/lib/semmle/python/dataflow/new/internal/TypeTracker.qll",
     "ruby/ql/lib/codeql/ruby/typetracking/TypeTracker.qll"
   ],
+  "CodeQL Tutorial": [
+    "cpp/ql/lib/tutorial.qll",
+    "csharp/ql/lib/tutorial.qll",
+    "java/ql/lib/tutorial.qll",
+    "javascript/ql/lib/tutorial.qll",
+    "python/ql/lib/tutorial.qll",
+    "ruby/ql/lib/tutorial.qll"
+  ],
   "AccessPathSyntax": [
     "csharp/ql/lib/semmle/code/csharp/dataflow/internal/AccessPathSyntax.qll",
     "go/ql/lib/semmle/go/dataflow/internal/AccessPathSyntax.qll",
@@ -514,16 +527,16 @@
     "ruby/ql/lib/codeql/ruby/internal/ConceptsShared.qll",
     "javascript/ql/lib/semmle/javascript/internal/ConceptsShared.qll"
   ],
+  "Hostname Regexp queries": [
+    "javascript/ql/src/Security/CWE-020/HostnameRegexpShared.qll",
+    "python/ql/src/Security/CWE-020/HostnameRegexpShared.qll",
+    "ruby/ql/src/queries/security/cwe-020/HostnameRegexpShared.qll"
+  ],
   "ApiGraphModels": [
     "javascript/ql/lib/semmle/javascript/frameworks/data/internal/ApiGraphModels.qll",
     "ruby/ql/lib/codeql/ruby/frameworks/data/internal/ApiGraphModels.qll",
     "python/ql/lib/semmle/python/frameworks/data/internal/ApiGraphModels.qll"
   ],
-  "ApiGraphModelsExtensions": [
-    "javascript/ql/lib/semmle/javascript/frameworks/data/internal/ApiGraphModelsExtensions.qll",
-    "ruby/ql/lib/codeql/ruby/frameworks/data/internal/ApiGraphModelsExtensions.qll",
-    "python/ql/lib/semmle/python/frameworks/data/internal/ApiGraphModelsExtensions.qll"
-  ],
   "TaintedFormatStringQuery Ruby/JS": [
     "javascript/ql/lib/semmle/javascript/security/dataflow/TaintedFormatStringQuery.qll",
     "ruby/ql/lib/codeql/ruby/security/TaintedFormatStringQuery.qll"
@@ -567,9 +580,5 @@
   "IncompleteMultiCharacterSanitization JS/Ruby": [
     "javascript/ql/lib/semmle/javascript/security/IncompleteMultiCharacterSanitizationQuery.qll",
     "ruby/ql/lib/codeql/ruby/security/IncompleteMultiCharacterSanitizationQuery.qll"
-  ],
-  "EncryptionKeySizes Python/Java": [
-    "python/ql/lib/semmle/python/security/internal/EncryptionKeySizes.qll",
-    "java/ql/lib/semmle/code/java/security/internal/EncryptionKeySizes.qll"
   ]
 }

cpp/autobuilder/Semmle.Autobuild.Cpp.Tests/Semmle.Autobuild.Cpp.Tests.csproj

@@ -2,7 +2,7 @@
 
   <PropertyGroup>
     <OutputType>Exe</OutputType>
-    <TargetFramework>net7.0</TargetFramework>
+    <TargetFramework>net6.0</TargetFramework>
     <GenerateAssemblyInfo>false</GenerateAssemblyInfo>
     <RuntimeIdentifiers>win-x64;linux-x64;osx-x64</RuntimeIdentifiers>
     <Nullable>enable</Nullable>

cpp/autobuilder/Semmle.Autobuild.Cpp/Semmle.Autobuild.Cpp.csproj

@@ -1,7 +1,7 @@
 <Project Sdk="Microsoft.NET.Sdk">
 
   <PropertyGroup>
-    <TargetFramework>net7.0</TargetFramework>
+    <TargetFramework>net6.0</TargetFramework>
     <AssemblyName>Semmle.Autobuild.Cpp</AssemblyName>
     <RootNamespace>Semmle.Autobuild.Cpp</RootNamespace>
     <ApplicationIcon />

cpp/downgrades/23f7cbb88a4eb29f30c3490363dc201bc054c5ff/exprs.ql

@@ -13,5 +13,5 @@ predicate isExprWithNewBuiltin(Expr expr) {
 from Expr expr, int kind, int kind_new, Location location
 where
   exprs(expr, kind, location) and
-  if isExprWithNewBuiltin(expr) then kind_new = 1 else kind_new = kind
+  if isExprWithNewBuiltin(expr) then kind_new = 0 else kind_new = kind
 select expr, kind_new, location

cpp/downgrades/73af5058c6899dcdb05754c27ca966aeb3a68c94/exprs.ql

@@ -9,5 +9,5 @@ class Location extends @location_expr {
 from Expr expr, int kind, int kind_new, Location location
 where
   exprs(expr, kind, location) and
-  if expr instanceof @blockassignexpr then kind_new = 1 else kind_new = kind
+  if expr instanceof @blockassignexpr then kind_new = 0 else kind_new = kind
 select expr, kind_new, location

cpp/downgrades/a5bb28ed29f73855d64cc5f939cef977fa8fd19a/builtintypes.ql

@@ -1,11 +0,0 @@
-class BuiltinType extends @builtintype {
-  string toString() { none() }
-}
-
-from BuiltinType type, string name, int kind, int kind_new, int size, int sign, int alignment
-where
-  builtintypes(type, name, kind, size, sign, alignment) and
-  if type instanceof @float16 or type instanceof @complex_float16
-  then kind_new = 2
-  else kind_new = kind
-select type, name, kind_new, size, sign, alignment

cpp/downgrades/a5bb28ed29f73855d64cc5f939cef977fa8fd19a/upgrade.properties

@@ -1,3 +0,0 @@
-description: Introduce (_Complex) _Float16 type
-compatibility: backwards
-builtintypes.rel: run builtintypes.qlo

cpp/downgrades/ba86bebea4c7a8235c2fa0e220391fbd4446a087/upgrade.properties

@@ -1,2 +0,0 @@
-description: Uncomment case splits in dbscheme
-compatibility: full

cpp/ql/lib/CHANGELOG.md

@@ -1,44 +1,3 @@
-## 0.5.3
-
-No user-facing changes.
-
-## 0.5.2
-
-No user-facing changes.
-
-## 0.5.1
-
-No user-facing changes.
-
-## 0.5.0
-
-### Breaking Changes
-
-The predicates in the `MustFlow::Configuration` class used by the `MustFlow` library (`semmle.code.cpp.ir.dataflow.MustFlow`) have changed to be defined directly in terms of the C++ IR instead of IR dataflow nodes.
-
-### Deprecated APIs
-
-* Deprecated `semmle.code.cpp.ir.dataflow.DefaultTaintTracking`. Use `semmle.code.cpp.ir.dataflow.TaintTracking`.
-* Deprecated `semmle.code.cpp.security.TaintTrackingImpl`. Use `semmle.code.cpp.ir.dataflow.TaintTracking`.
-* Deprecated `semmle.code.cpp.valuenumbering.GlobalValueNumberingImpl`. Use `semmle.code.cpp.valuenumbering.GlobalValueNumbering`, which exposes the same API.
-
-### Minor Analysis Improvements
-
-* The `ArgvSource` flow source now uses the second parameter of `main` as its source instead of the uses of this parameter.
-* The `ArgvSource` flow source has been generalized to handle cases where the argument vector of `main` is not named `argv`.
-* The `getaddrinfo` function is now recognized as a flow source.
-* The `secure_getenv` and `_wgetenv` functions are now recognized as local flow sources.
-* The `scanf` and `fscanf` functions and their variants are now recognized as flow sources.
-* Deleted the deprecated `getName` and `getShortName` predicates from the `Folder` class.
-
-## 0.4.6
-
-No user-facing changes.
-
-## 0.4.5
-
-No user-facing changes.
-
 ## 0.4.4
 
 No user-facing changes.

cpp/ql/lib/change-notes/2022-11-14-deprecate-ast-gvn.md

@@ -0,0 +1,6 @@
+---
+category: deprecated
+---
+
+
+* Deprecated `semmle.code.cpp.valuenumbering.GlobalValueNumberingImpl`. Use `semmle.code.cpp.valuenumbering.GlobalValueNumbering`, which exposes the same API.

cpp/ql/lib/change-notes/2022-11-16-must-flow.md

@@ -0,0 +1,4 @@
+---
+category: breaking
+---
+The predicates in the `MustFlow::Configuration` class used by the `MustFlow` library (`semmle.code.cpp.ir.dataflow.MustFlow`) have changed to be defined directly in terms of the C++ IR instead of IR dataflow nodes.

cpp/ql/lib/change-notes/2022-11-17-deleted-deps.md

@@ -0,0 +1,4 @@
+---
+category: minorAnalysis
+---
+* Deleted the deprecated `getName` and `getShortName` predicates from the `Folder` class.

cpp/ql/lib/change-notes/released/0.4.5.md

@@ -1,3 +0,0 @@
-## 0.4.5
-
-No user-facing changes.

cpp/ql/lib/change-notes/released/0.4.6.md

@@ -1,3 +0,0 @@
-## 0.4.6
-
-No user-facing changes.

cpp/ql/lib/change-notes/released/0.5.0.md

@@ -1,20 +0,0 @@
-## 0.5.0
-
-### Breaking Changes
-
-The predicates in the `MustFlow::Configuration` class used by the `MustFlow` library (`semmle.code.cpp.ir.dataflow.MustFlow`) have changed to be defined directly in terms of the C++ IR instead of IR dataflow nodes.
-
-### Deprecated APIs
-
-* Deprecated `semmle.code.cpp.ir.dataflow.DefaultTaintTracking`. Use `semmle.code.cpp.ir.dataflow.TaintTracking`.
-* Deprecated `semmle.code.cpp.security.TaintTrackingImpl`. Use `semmle.code.cpp.ir.dataflow.TaintTracking`.
-* Deprecated `semmle.code.cpp.valuenumbering.GlobalValueNumberingImpl`. Use `semmle.code.cpp.valuenumbering.GlobalValueNumbering`, which exposes the same API.
-
-### Minor Analysis Improvements
-
-* The `ArgvSource` flow source now uses the second parameter of `main` as its source instead of the uses of this parameter.
-* The `ArgvSource` flow source has been generalized to handle cases where the argument vector of `main` is not named `argv`.
-* The `getaddrinfo` function is now recognized as a flow source.
-* The `secure_getenv` and `_wgetenv` functions are now recognized as local flow sources.
-* The `scanf` and `fscanf` functions and their variants are now recognized as flow sources.
-* Deleted the deprecated `getName` and `getShortName` predicates from the `Folder` class.

cpp/ql/lib/change-notes/released/0.5.1.md

@@ -1,3 +0,0 @@
-## 0.5.1
-
-No user-facing changes.

cpp/ql/lib/change-notes/released/0.5.2.md

@@ -1,3 +0,0 @@
-## 0.5.2
-
-No user-facing changes.

cpp/ql/lib/change-notes/released/0.5.3.md

@@ -1,3 +0,0 @@
-## 0.5.3
-
-No user-facing changes.

cpp/ql/lib/codeql-pack.release.yml

@@ -1,2 +1,2 @@
 ---
-lastReleaseVersion: 0.5.3
+lastReleaseVersion: 0.4.4

cpp/ql/lib/definitions.qll

@@ -123,13 +123,6 @@ private predicate constructorCallTypeMention(ConstructorCall cc, TypeMention tm)
   )
 }
 
-/** Holds if `loc` has the container `container` and is on the line starting at `startLine`. */
-pragma[nomagic]
-private predicate hasContainerAndStartLine(Location loc, Container container, int startLine) {
-  loc.getStartLine() = startLine and
-  loc.getContainer() = container
-}
-
 /**
  * Gets an element, of kind `kind`, that element `e` uses, if any.
  * Attention: This predicate yields multiple definitions for a single location.
@@ -166,9 +159,9 @@ Top definitionOf(Top e, string kind) {
     // Multiple type mentions can be generated when a typedef is used, and
     // in such cases we want to exclude all but the originating typedef.
     not exists(Type secondary |
-      exists(File f, int startline, int startcol |
+      exists(TypeMention tm, File f, int startline, int startcol |
         typeMentionStartLoc(e, result, f, startline, startcol) and
-        typeMentionStartLoc(_, secondary, f, startline, startcol) and
+        typeMentionStartLoc(tm, secondary, f, startline, startcol) and
         (
           result = secondary.(TypedefType).getBaseType() or
           result = secondary.(TypedefType).getBaseType().(SpecifiedType).getBaseType()
@@ -191,9 +184,11 @@ Top definitionOf(Top e, string kind) {
     kind = "I" and
     result = e.(Include).getIncludedFile() and
     // exclude `#include` directives containing macros
-    not exists(MacroInvocation mi, Container container, int startLine |
-      hasContainerAndStartLine(e.(Include).getLocation(), container, startLine) and
-      hasContainerAndStartLine(mi.getLocation(), container, startLine)
+    not exists(MacroInvocation mi, Location l1, Location l2 |
+      l1 = e.(Include).getLocation() and
+      l2 = mi.getLocation() and
+      l1.getContainer() = l2.getContainer() and
+      l1.getStartLine() = l2.getStartLine()
       // (an #include directive must be always on it's own line)
     )
   ) and

cpp/ql/lib/experimental/semmle/code/cpp/ir/dataflow/internal/DataFlowImplCommon.qll

@@ -707,8 +707,8 @@ private module Cached {
      * Gets a viable dispatch target of `call` in the context `ctx`. This is
      * restricted to those `call`s for which a context might make a difference.
      */
-    cached
-    DataFlowCallable viableImplInCallContextExt(DataFlowCall call, DataFlowCall ctx) {
+    pragma[nomagic]
+    private DataFlowCallable viableImplInCallContextExt(DataFlowCall call, DataFlowCall ctx) {
       result = viableImplInCallContext(call, ctx) and
       result = viableCallable(call)
       or
@@ -916,56 +916,28 @@ private module Cached {
     TDataFlowCallSome(DataFlowCall call)
 
   cached
-  newtype TParamNodeOption =
-    TParamNodeNone() or
-    TParamNodeSome(ParamNode p)
+  newtype TParameterPositionOption =
+    TParameterPositionNone() or
+    TParameterPositionSome(ParameterPosition pos)
 
   cached
   newtype TReturnCtx =
     TReturnCtxNone() or
     TReturnCtxNoFlowThrough() or
-    TReturnCtxMaybeFlowThrough(ReturnPosition pos)
-
-  cached
-  newtype TTypedContentApprox =
-    MkTypedContentApprox(ContentApprox c, DataFlowType t) {
-      exists(Content cont |
-        c = getContentApprox(cont) and
-        store(_, cont, _, _, t)
-      )
-    }
+    TReturnCtxMaybeFlowThrough(ReturnKindExt kind)
 
   cached
   newtype TTypedContent = MkTypedContent(Content c, DataFlowType t) { store(_, c, _, _, t) }
 
-  cached
-  TypedContent getATypedContent(TypedContentApprox c) {
-    exists(ContentApprox cls, DataFlowType t, Content cont |
-      c = MkTypedContentApprox(cls, pragma[only_bind_into](t)) and
-      result = MkTypedContent(cont, pragma[only_bind_into](t)) and
-      cls = getContentApprox(cont)
-    )
-  }
-
   cached
   newtype TAccessPathFront =
     TFrontNil(DataFlowType t) or
     TFrontHead(TypedContent tc)
 
-  cached
-  newtype TApproxAccessPathFront =
-    TApproxFrontNil(DataFlowType t) or
-    TApproxFrontHead(TypedContentApprox tc)
-
   cached
   newtype TAccessPathFrontOption =
     TAccessPathFrontNone() or
     TAccessPathFrontSome(AccessPathFront apf)
-
-  cached
-  newtype TApproxAccessPathFrontOption =
-    TApproxAccessPathFrontNone() or
-    TApproxAccessPathFrontSome(ApproxAccessPathFront apf)
 }
 
 /**
@@ -1343,15 +1315,15 @@ class DataFlowCallOption extends TDataFlowCallOption {
   }
 }
 
-/** An optional `ParamNode`. */
-class ParamNodeOption extends TParamNodeOption {
+/** An optional `ParameterPosition`. */
+class ParameterPositionOption extends TParameterPositionOption {
   string toString() {
-    this = TParamNodeNone() and
+    this = TParameterPositionNone() and
     result = "(none)"
     or
-    exists(ParamNode p |
-      this = TParamNodeSome(p) and
-      result = p.toString()
+    exists(ParameterPosition pos |
+      this = TParameterPositionSome(pos) and
+      result = pos.toString()
     )
   }
 }
@@ -1363,7 +1335,7 @@ class ParamNodeOption extends TParamNodeOption {
  *
  * - `TReturnCtxNone()`: no return flow.
  * - `TReturnCtxNoFlowThrough()`: return flow, but flow through is not possible.
- * - `TReturnCtxMaybeFlowThrough(ReturnPosition pos)`: return flow, of kind `pos`, and
+ * - `TReturnCtxMaybeFlowThrough(ReturnKindExt kind)`: return flow, of kind `kind`, and
  *    flow through may be possible.
  */
 class ReturnCtx extends TReturnCtx {
@@ -1374,87 +1346,13 @@ class ReturnCtx extends TReturnCtx {
     this = TReturnCtxNoFlowThrough() and
     result = "(no flow through)"
     or
-    exists(ReturnPosition pos |
-      this = TReturnCtxMaybeFlowThrough(pos) and
-      result = pos.toString()
+    exists(ReturnKindExt kind |
+      this = TReturnCtxMaybeFlowThrough(kind) and
+      result = kind.toString()
     )
   }
 }
 
-/** An approximated `Content` tagged with the type of a containing object. */
-class TypedContentApprox extends MkTypedContentApprox {
-  private ContentApprox c;
-  private DataFlowType t;
-
-  TypedContentApprox() { this = MkTypedContentApprox(c, t) }
-
-  /** Gets a typed content approximated by this value. */
-  TypedContent getATypedContent() { result = getATypedContent(this) }
-
-  /** Gets the content. */
-  ContentApprox getContent() { result = c }
-
-  /** Gets the container type. */
-  DataFlowType getContainerType() { result = t }
-
-  /** Gets a textual representation of this approximated content. */
-  string toString() { result = c.toString() }
-}
-
-/**
- * The front of an approximated access path. This is either a head or a nil.
- */
-abstract class ApproxAccessPathFront extends TApproxAccessPathFront {
-  abstract string toString();
-
-  abstract DataFlowType getType();
-
-  abstract boolean toBoolNonEmpty();
-
-  TypedContentApprox getHead() { this = TApproxFrontHead(result) }
-
-  pragma[nomagic]
-  TypedContent getAHead() {
-    exists(TypedContentApprox cont |
-      this = TApproxFrontHead(cont) and
-      result = cont.getATypedContent()
-    )
-  }
-}
-
-class ApproxAccessPathFrontNil extends ApproxAccessPathFront, TApproxFrontNil {
-  private DataFlowType t;
-
-  ApproxAccessPathFrontNil() { this = TApproxFrontNil(t) }
-
-  override string toString() { result = ppReprType(t) }
-
-  override DataFlowType getType() { result = t }
-
-  override boolean toBoolNonEmpty() { result = false }
-}
-
-class ApproxAccessPathFrontHead extends ApproxAccessPathFront, TApproxFrontHead {
-  private TypedContentApprox tc;
-
-  ApproxAccessPathFrontHead() { this = TApproxFrontHead(tc) }
-
-  override string toString() { result = tc.toString() }
-
-  override DataFlowType getType() { result = tc.getContainerType() }
-
-  override boolean toBoolNonEmpty() { result = true }
-}
-
-/** An optional approximated access path front. */
-class ApproxAccessPathFrontOption extends TApproxAccessPathFrontOption {
-  string toString() {
-    this = TApproxAccessPathFrontNone() and result = "<none>"
-    or
-    this = TApproxAccessPathFrontSome(any(ApproxAccessPathFront apf | result = apf.toString()))
-  }
-}
-
 /** A `Content` tagged with the type of a containing object. */
 class TypedContent extends MkTypedContent {
   private Content c;
@@ -1487,7 +1385,7 @@ abstract class AccessPathFront extends TAccessPathFront {
 
   abstract DataFlowType getType();
 
-  abstract ApproxAccessPathFront toApprox();
+  abstract boolean toBoolNonEmpty();
 
   TypedContent getHead() { this = TFrontHead(result) }
 }
@@ -1501,7 +1399,7 @@ class AccessPathFrontNil extends AccessPathFront, TFrontNil {
 
   override DataFlowType getType() { result = t }
 
-  override ApproxAccessPathFront toApprox() { result = TApproxFrontNil(t) }
+  override boolean toBoolNonEmpty() { result = false }
 }
 
 class AccessPathFrontHead extends AccessPathFront, TFrontHead {
@@ -1513,7 +1411,7 @@ class AccessPathFrontHead extends AccessPathFront, TFrontHead {
 
   override DataFlowType getType() { result = tc.getContainerType() }
 
-  override ApproxAccessPathFront toApprox() { result.getAHead() = tc }
+  override boolean toBoolNonEmpty() { result = true }
 }
 
 /** An optional access path front. */

cpp/ql/lib/experimental/semmle/code/cpp/ir/dataflow/internal/DataFlowImplConsistency.qll

@@ -45,16 +45,6 @@ module Consistency {
     ) {
       none()
     }
-
-    /** Holds if `(c, pos, p)` should be excluded from the consistency test `uniqueParameterNodeAtPosition`. */
-    predicate uniqueParameterNodeAtPositionExclude(DataFlowCallable c, ParameterPosition pos, Node p) {
-      none()
-    }
-
-    /** Holds if `(c, pos, p)` should be excluded from the consistency test `uniqueParameterNodePosition`. */
-    predicate uniqueParameterNodePositionExclude(DataFlowCallable c, ParameterPosition pos, Node p) {
-      none()
-    }
   }
 
   private class RelevantNode extends Node {
@@ -111,7 +101,9 @@ module Consistency {
     exists(int c |
       c =
         strictcount(Node n |
-          not n.hasLocationInfo(_, _, _, _, _) and
+          not exists(string filepath, int startline, int startcolumn, int endline, int endcolumn |
+            n.hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
+          ) and
           not any(ConsistencyConfiguration conf).missingLocationExclude(n)
         ) and
       msg = "Nodes without location: " + c
@@ -256,7 +248,6 @@ module Consistency {
   query predicate uniqueParameterNodeAtPosition(
     DataFlowCallable c, ParameterPosition pos, Node p, string msg
   ) {
-    not any(ConsistencyConfiguration conf).uniqueParameterNodeAtPositionExclude(c, pos, p) and
     isParameterNode(p, c, pos) and
     not exists(unique(Node p0 | isParameterNode(p0, c, pos))) and
     msg = "Parameters with overlapping positions."
@@ -265,14 +256,8 @@ module Consistency {
   query predicate uniqueParameterNodePosition(
     DataFlowCallable c, ParameterPosition pos, Node p, string msg
   ) {
-    not any(ConsistencyConfiguration conf).uniqueParameterNodePositionExclude(c, pos, p) and
     isParameterNode(p, c, pos) and
     not exists(unique(ParameterPosition pos0 | isParameterNode(p, c, pos0))) and
     msg = "Parameter node with multiple positions."
   }
-
-  query predicate uniqueContentApprox(Content c, string msg) {
-    not exists(unique(ContentApprox approx | approx = getContentApprox(c))) and
-    msg = "Non-unique content approximation."
-  }
 }

cpp/ql/lib/experimental/semmle/code/cpp/ir/dataflow/internal/DataFlowPrivate.qll

@@ -551,13 +551,6 @@ predicate additionalLambdaFlowStep(Node nodeFrom, Node nodeTo, boolean preserves
  */
 predicate allowParameterReturnInSelf(ParameterNode p) { none() }
 
-/** An approximated `Content`. */
-class ContentApprox = Unit;
-
-/** Gets an approximated value for content `c`. */
-pragma[inline]
-ContentApprox getContentApprox(Content c) { any() }
-
 private class MyConsistencyConfiguration extends Consistency::ConsistencyConfiguration {
   override predicate argHasPostUpdateExclude(ArgumentNode n) {
     // The rules for whether an IR argument gets a post-update node are too

cpp/ql/lib/experimental/semmle/code/cpp/rangeanalysis/ArrayLengthAnalysis.qll

@@ -218,7 +218,7 @@ private predicate allocation(Instruction array, Length length, int delta) {
           length.(VNLength).getInstruction().getConvertedResultExpression() = lengthExpr
         )
         or
-        not deconstructMallocSizeExpr(alloc.getSizeExpr(), _, _) and
+        not exists(int d | deconstructMallocSizeExpr(alloc.getSizeExpr(), _, d)) and
         length.(VNLength).getInstruction().getConvertedResultExpression() = alloc.getSizeExpr() and
         delta = 0
       )

cpp/ql/lib/experimental/semmle/code/cpp/rangeanalysis/RangeAnalysis.qll

@@ -543,7 +543,9 @@ private predicate boundedPhiCand(
   PhiInstruction phi, boolean upper, Bound b, int delta, boolean fromBackEdge, int origdelta,
   Reason reason
 ) {
-  boundedPhiInp(phi, _, b, delta, upper, fromBackEdge, origdelta, reason)
+  exists(PhiInputOperand op |
+    boundedPhiInp(phi, op, b, delta, upper, fromBackEdge, origdelta, reason)
+  )
 }
 
 /**

cpp/ql/lib/experimental/semmle/code/cpp/rangeanalysis/extensions/ConstantShiftExprRange.qll

@@ -1,263 +0,0 @@
-private import cpp
-private import experimental.semmle.code.cpp.models.interfaces.SimpleRangeAnalysisExpr
-private import semmle.code.cpp.rangeanalysis.RangeAnalysisUtils
-
-float evaluateConstantExpr(Expr e) {
-  result = e.getValue().toFloat()
-  or
-  // This handles when a constant value is put into a variable
-  // and the variable is used later
-  exists(SsaDefinition defn, StackVariable sv |
-    defn.getAUse(sv) = e and
-    result = defn.getDefiningValue(sv).getValue().toFloat()
-  )
-}
-
-// If the constant right operand is negative or is greater than or equal to the number of
-// bits in the left operands type, then the result is undefined (except on the IA-32
-// architecture where the shift value is masked with 0b00011111, but we can't
-// assume the architecture).
-bindingset[val]
-private predicate isValidShiftExprShift(float val, Expr l) {
-  val >= 0 and
-  // We use getFullyConverted because the spec says to use the *promoted* left operand
-  val < (l.getFullyConverted().getUnderlyingType().getSize() * 8)
-}
-
-bindingset[val, shift, max_val]
-private predicate canLShiftOverflow(int val, int shift, int max_val) {
-  // val << shift = val * 2^shift > max_val => val > max_val/2^shift = max_val >> b
-  val > max_val.bitShiftRight(shift)
-}
-
-/**
- * A range analysis expression consisting of the `>>` or `>>=` operator when at least
- * one operand is a constant (and if the right operand is a constant, it must be "valid"
- * (see `isValidShiftExprShift`)). When handling any undefined behavior, it leaves the
- * values unconstrained. From the C++ standard: "The behavior is undefined if the right
- * operand is negative, or greater than or equal to the length in bits of the promoted
- * left operand. The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an
- * unsigned type or if E1 has a signed type and a non-negative value, the value of the
- * result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a
- * negative value, the resulting value is implementation-defined."
- */
-class ConstantRShiftExprRange extends SimpleRangeAnalysisExpr {
-  /**
-   * Holds for `a >> b` or `a >>= b` in one of the following two cases:
-   * 1. `a` is a constant and `b` is not
-   * 2. `b` is constant
-   *
-   * We don't handle the case where `a` and `b` are both non-constant values.
-   */
-  ConstantRShiftExprRange() {
-    getUnspecifiedType() instanceof IntegralType and
-    exists(Expr l, Expr r |
-      l = this.(RShiftExpr).getLeftOperand() and
-      r = this.(RShiftExpr).getRightOperand()
-      or
-      l = this.(AssignRShiftExpr).getLValue() and
-      r = this.(AssignRShiftExpr).getRValue()
-    |
-      l.getUnspecifiedType() instanceof IntegralType and
-      r.getUnspecifiedType() instanceof IntegralType and
-      (
-        // If the left operand is a constant, verify that the right operand is not a constant
-        exists(evaluateConstantExpr(l)) and not exists(evaluateConstantExpr(r))
-        or
-        // If the right operand is a constant, check if it is a valid shift expression
-        exists(float constROp |
-          constROp = evaluateConstantExpr(r) and isValidShiftExprShift(constROp, l)
-        )
-      )
-    )
-  }
-
-  Expr getLeftOperand() {
-    result = this.(RShiftExpr).getLeftOperand() or
-    result = this.(AssignRShiftExpr).getLValue()
-  }
-
-  Expr getRightOperand() {
-    result = this.(RShiftExpr).getRightOperand() or
-    result = this.(AssignRShiftExpr).getRValue()
-  }
-
-  override float getLowerBounds() {
-    exists(int lLower, int lUpper, int rLower, int rUpper |
-      lLower = getFullyConvertedLowerBounds(getLeftOperand()) and
-      lUpper = getFullyConvertedUpperBounds(getLeftOperand()) and
-      rLower = getFullyConvertedLowerBounds(getRightOperand()) and
-      rUpper = getFullyConvertedUpperBounds(getRightOperand()) and
-      lLower <= lUpper and
-      rLower <= rUpper
-    |
-      if
-        lLower < 0
-        or
-        not (
-          isValidShiftExprShift(rLower, getLeftOperand()) and
-          isValidShiftExprShift(rUpper, getLeftOperand())
-        )
-      then
-        // We don't want to deal with shifting negative numbers at the moment,
-        // and a negative shift is implementation defined, so we set the result
-        // to the minimum value
-        result = exprMinVal(this)
-      else
-        // We can get the smallest value by shifting the smallest bound by the largest bound
-        result = lLower.bitShiftRight(rUpper)
-    )
-  }
-
-  override float getUpperBounds() {
-    exists(int lLower, int lUpper, int rLower, int rUpper |
-      lLower = getFullyConvertedLowerBounds(getLeftOperand()) and
-      lUpper = getFullyConvertedUpperBounds(getLeftOperand()) and
-      rLower = getFullyConvertedLowerBounds(getRightOperand()) and
-      rUpper = getFullyConvertedUpperBounds(getRightOperand()) and
-      lLower <= lUpper and
-      rLower <= rUpper
-    |
-      if
-        lLower < 0
-        or
-        not (
-          isValidShiftExprShift(rLower, getLeftOperand()) and
-          isValidShiftExprShift(rUpper, getLeftOperand())
-        )
-      then
-        // We don't want to deal with shifting negative numbers at the moment,
-        // and a negative shift is implementation defined, so we set the result
-        // to the maximum value
-        result = exprMaxVal(this)
-      else
-        // We can get the largest value by shifting the largest bound by the smallest bound
-        result = lUpper.bitShiftRight(rLower)
-    )
-  }
-
-  override predicate dependsOnChild(Expr child) {
-    child = getLeftOperand() or child = getRightOperand()
-  }
-}
-
-/**
- * A range analysis expression consisting of the `<<` or `<<=` operator when at least
- * one operand is a constant (and if the right operand is a constant, it must be "valid"
- * (see `isValidShiftExprShift`)). When handling any undefined behavior, it leaves the
- * values unconstrained. From the C++ standard: "The behavior is undefined if the right
- * operand is negative, or greater than or equal to the length in bits of the promoted left operand.
- * The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1
- * has an unsigned type, the value of the result is E1 x 2 E2, reduced modulo one more than the
- * maximum value representable in the result type. Otherwise, if E1 has a signed type and
- * non-negative value, and E1 x 2 E2 is representable in the corresponding unsigned type of the
- * result type, then that value, converted to the result type, is the resulting value; otherwise,
- * the behavior is undefined."
- */
-class ConstantLShiftExprRange extends SimpleRangeAnalysisExpr {
-  /**
-   * Holds for `a << b` or `a <<= b` in one of the following two cases:
-   * 1. `a` is a constant and `b` is not
-   * 2. `b` is constant
-   *
-   * We don't handle the case where `a` and `b` are both non-constant values.
-   */
-  ConstantLShiftExprRange() {
-    getUnspecifiedType() instanceof IntegralType and
-    exists(Expr l, Expr r |
-      l = this.(LShiftExpr).getLeftOperand() and
-      r = this.(LShiftExpr).getRightOperand()
-      or
-      l = this.(AssignLShiftExpr).getLValue() and
-      r = this.(AssignLShiftExpr).getRValue()
-    |
-      l.getUnspecifiedType() instanceof IntegralType and
-      r.getUnspecifiedType() instanceof IntegralType and
-      (
-        // If the left operand is a constant, verify that the right operand is not a constant
-        exists(evaluateConstantExpr(l)) and not exists(evaluateConstantExpr(r))
-        or
-        // If the right operand is a constant, check if it is a valid shift expression
-        exists(float constROp |
-          constROp = evaluateConstantExpr(r) and isValidShiftExprShift(constROp, l)
-        )
-      )
-    )
-  }
-
-  Expr getLeftOperand() {
-    result = this.(LShiftExpr).getLeftOperand() or
-    result = this.(AssignLShiftExpr).getLValue()
-  }
-
-  Expr getRightOperand() {
-    result = this.(LShiftExpr).getRightOperand() or
-    result = this.(AssignLShiftExpr).getRValue()
-  }
-
-  override float getLowerBounds() {
-    exists(int lLower, int lUpper, int rLower, int rUpper |
-      lLower = getFullyConvertedLowerBounds(getLeftOperand()) and
-      lUpper = getFullyConvertedUpperBounds(getLeftOperand()) and
-      rLower = getFullyConvertedLowerBounds(getRightOperand()) and
-      rUpper = getFullyConvertedUpperBounds(getRightOperand()) and
-      lLower <= lUpper and
-      rLower <= rUpper
-    |
-      if
-        lLower < 0
-        or
-        not (
-          isValidShiftExprShift(rLower, getLeftOperand()) and
-          isValidShiftExprShift(rUpper, getLeftOperand())
-        )
-      then
-        // We don't want to deal with shifting negative numbers at the moment,
-        // and a negative shift is undefined, so we set to the minimum value
-        result = exprMinVal(this)
-      else
-        // If we have `0b01010000 << [0, 2]`, the max value for 8 bits is 0b10100000
-        // (a shift of 1) but doing a shift by the upper bound would give 0b01000000.
-        // So if the left shift operation causes an overflow, we just assume the max value
-        // If necessary, we may be able to improve this bound in the future
-        if canLShiftOverflow(lUpper, rUpper, exprMaxVal(this))
-        then result = exprMinVal(this)
-        else result = lLower.bitShiftLeft(rLower)
-    )
-  }
-
-  override float getUpperBounds() {
-    exists(int lLower, int lUpper, int rLower, int rUpper |
-      lLower = getFullyConvertedLowerBounds(getLeftOperand()) and
-      lUpper = getFullyConvertedUpperBounds(getLeftOperand()) and
-      rLower = getFullyConvertedLowerBounds(getRightOperand()) and
-      rUpper = getFullyConvertedUpperBounds(getRightOperand()) and
-      lLower <= lUpper and
-      rLower <= rUpper
-    |
-      if
-        lLower < 0
-        or
-        not (
-          isValidShiftExprShift(rLower, getLeftOperand()) and
-          isValidShiftExprShift(rUpper, getLeftOperand())
-        )
-      then
-        // We don't want to deal with shifting negative numbers at the moment,
-        // and a negative shift is undefined, so we set it to the maximum value
-        result = exprMaxVal(this)
-      else
-        // If we have `0b01010000 << [0, 2]`, the max value for 8 bits is 0b10100000
-        // (a shift of 1) but doing a shift by the upper bound would give 0b01000000.
-        // So if the left shift operation causes an overflow, we just assume the max value
-        // If necessary, we may be able to improve this bound in the future
-        if canLShiftOverflow(lUpper, rUpper, exprMaxVal(this))
-        then result = exprMaxVal(this)
-        else result = lUpper.bitShiftLeft(rUpper)
-    )
-  }
-
-  override predicate dependsOnChild(Expr child) {
-    child = getLeftOperand() or child = getRightOperand()
-  }
-}

cpp/ql/lib/experimental/semmle/code/cpp/semantic/SemanticExprSpecific.qll

@@ -292,8 +292,12 @@ module SemanticExprConfig {
     final Location getLocation() { result = super.getLocation() }
   }
 
-  private class ValueNumberBound extends Bound instanceof IRBound::ValueNumberBound {
-    override string toString() { result = IRBound::ValueNumberBound.super.toString() }
+  private class ValueNumberBound extends Bound {
+    IRBound::ValueNumberBound bound;
+
+    ValueNumberBound() { bound = this }
+
+    override string toString() { result = bound.toString() }
   }
 
   predicate zeroBound(Bound bound) { bound instanceof IRBound::ZeroBound }

cpp/ql/lib/experimental/semmle/code/cpp/semantic/analysis/FloatDelta.qll

@@ -1,29 +0,0 @@
-private import RangeAnalysisStage
-
-module FloatDelta implements DeltaSig {
-  class Delta = float;
-
-  bindingset[d]
-  bindingset[result]
-  float toFloat(Delta d) { result = d }
-
-  bindingset[d]
-  bindingset[result]
-  int toInt(Delta d) { result = d }
-
-  bindingset[n]
-  bindingset[result]
-  Delta fromInt(int n) { result = n }
-
-  bindingset[f]
-  Delta fromFloat(float f) {
-    result =
-      min(float diff, float res |
-        diff = (res - f) and res = f.ceil()
-        or
-        diff = (f - res) and res = f.floor()
-      |
-        res order by diff
-      )
-  }
-}

cpp/ql/lib/experimental/semmle/code/cpp/semantic/analysis/ModulusAnalysis.qll

@@ -14,328 +14,321 @@ private import ModulusAnalysisSpecific::Private
 private import experimental.semmle.code.cpp.semantic.Semantic
 private import ConstantAnalysis
 private import RangeUtils
-private import RangeAnalysisStage
 
-module ModulusAnalysis<DeltaSig D, BoundSig<D> Bounds, UtilSig<D> U> {
-  /**
-   * Holds if `e + delta` equals `v` at `pos`.
-   */
-  private predicate valueFlowStepSsa(SemSsaVariable v, SemSsaReadPosition pos, SemExpr e, int delta) {
-    U::semSsaUpdateStep(v, e, D::fromInt(delta)) and pos.hasReadOfVar(v)
-    or
-    exists(SemGuard guard, boolean testIsTrue |
-      pos.hasReadOfVar(v) and
-      guard = U::semEqFlowCond(v, e, D::fromInt(delta), true, testIsTrue) and
-      semGuardDirectlyControlsSsaRead(guard, pos, testIsTrue)
-    )
-  }
+/**
+ * Holds if `e + delta` equals `v` at `pos`.
+ */
+private predicate valueFlowStepSsa(SemSsaVariable v, SemSsaReadPosition pos, SemExpr e, int delta) {
+  semSsaUpdateStep(v, e, delta) and pos.hasReadOfVar(v)
+  or
+  exists(SemGuard guard, boolean testIsTrue |
+    pos.hasReadOfVar(v) and
+    guard = semEqFlowCond(v, e, delta, true, testIsTrue) and
+    semGuardDirectlyControlsSsaRead(guard, pos, testIsTrue)
+  )
+}
 
-  /**
-   * Holds if `add` is the addition of `larg` and `rarg`, neither of which are
-   * `ConstantIntegerExpr`s.
-   */
-  private predicate nonConstAddition(SemExpr add, SemExpr larg, SemExpr rarg) {
-    exists(SemAddExpr a | a = add |
-      larg = a.getLeftOperand() and
-      rarg = a.getRightOperand()
-    ) and
-    not larg instanceof SemConstantIntegerExpr and
-    not rarg instanceof SemConstantIntegerExpr
-  }
+/**
+ * Holds if `add` is the addition of `larg` and `rarg`, neither of which are
+ * `ConstantIntegerExpr`s.
+ */
+private predicate nonConstAddition(SemExpr add, SemExpr larg, SemExpr rarg) {
+  exists(SemAddExpr a | a = add |
+    larg = a.getLeftOperand() and
+    rarg = a.getRightOperand()
+  ) and
+  not larg instanceof SemConstantIntegerExpr and
+  not rarg instanceof SemConstantIntegerExpr
+}
 
-  /**
-   * Holds if `sub` is the subtraction of `larg` and `rarg`, where `rarg` is not
-   * a `ConstantIntegerExpr`.
-   */
-  private predicate nonConstSubtraction(SemExpr sub, SemExpr larg, SemExpr rarg) {
-    exists(SemSubExpr s | s = sub |
-      larg = s.getLeftOperand() and
-      rarg = s.getRightOperand()
-    ) and
-    not rarg instanceof SemConstantIntegerExpr
-  }
+/**
+ * Holds if `sub` is the subtraction of `larg` and `rarg`, where `rarg` is not
+ * a `ConstantIntegerExpr`.
+ */
+private predicate nonConstSubtraction(SemExpr sub, SemExpr larg, SemExpr rarg) {
+  exists(SemSubExpr s | s = sub |
+    larg = s.getLeftOperand() and
+    rarg = s.getRightOperand()
+  ) and
+  not rarg instanceof SemConstantIntegerExpr
+}
 
-  /** Gets an expression that is the remainder modulo `mod` of `arg`. */
-  private SemExpr modExpr(SemExpr arg, int mod) {
-    exists(SemRemExpr rem |
-      result = rem and
-      arg = rem.getLeftOperand() and
-      rem.getRightOperand().(SemConstantIntegerExpr).getIntValue() = mod and
-      mod >= 2
-    )
-    or
-    exists(SemConstantIntegerExpr c |
-      mod = 2.pow([1 .. 30]) and
-      c.getIntValue() = mod - 1 and
-      result.(SemBitAndExpr).hasOperands(arg, c)
-    )
-  }
+/** Gets an expression that is the remainder modulo `mod` of `arg`. */
+private SemExpr modExpr(SemExpr arg, int mod) {
+  exists(SemRemExpr rem |
+    result = rem and
+    arg = rem.getLeftOperand() and
+    rem.getRightOperand().(SemConstantIntegerExpr).getIntValue() = mod and
+    mod >= 2
+  )
+  or
+  exists(SemConstantIntegerExpr c |
+    mod = 2.pow([1 .. 30]) and
+    c.getIntValue() = mod - 1 and
+    result.(SemBitAndExpr).hasOperands(arg, c)
+  )
+}
 
-  /**
-   * Gets a guard that tests whether `v` is congruent with `val` modulo `mod` on
-   * its `testIsTrue` branch.
-   */
-  private SemGuard moduloCheck(SemSsaVariable v, int val, int mod, boolean testIsTrue) {
-    exists(SemExpr rem, SemConstantIntegerExpr c, int r, boolean polarity |
-      result.isEquality(rem, c, polarity) and
-      c.getIntValue() = r and
-      rem = modExpr(v.getAUse(), mod) and
-      (
-        testIsTrue = polarity and val = r
-        or
-        testIsTrue = polarity.booleanNot() and
-        mod = 2 and
-        val = 1 - r and
-        (r = 0 or r = 1)
-      )
-    )
-  }
-
-  /**
-   * Holds if a guard ensures that `v` at `pos` is congruent with `val` modulo `mod`.
-   */
-  private predicate moduloGuardedRead(SemSsaVariable v, SemSsaReadPosition pos, int val, int mod) {
-    exists(SemGuard guard, boolean testIsTrue |
-      pos.hasReadOfVar(v) and
-      guard = moduloCheck(v, val, mod, testIsTrue) and
-      semGuardControlsSsaRead(guard, pos, testIsTrue)
-    )
-  }
-
-  /** Holds if `factor` is a power of 2 that divides `mask`. */
-  bindingset[mask]
-  private predicate andmaskFactor(int mask, int factor) {
-    mask % factor = 0 and
-    factor = 2.pow([1 .. 30])
-  }
-
-  /** Holds if `e` is evenly divisible by `factor`. */
-  private predicate evenlyDivisibleExpr(SemExpr e, int factor) {
-    exists(SemConstantIntegerExpr c, int k | k = c.getIntValue() |
-      e.(SemMulExpr).getAnOperand() = c and factor = k.abs() and factor >= 2
+/**
+ * Gets a guard that tests whether `v` is congruent with `val` modulo `mod` on
+ * its `testIsTrue` branch.
+ */
+private SemGuard moduloCheck(SemSsaVariable v, int val, int mod, boolean testIsTrue) {
+  exists(SemExpr rem, SemConstantIntegerExpr c, int r, boolean polarity |
+    result.isEquality(rem, c, polarity) and
+    c.getIntValue() = r and
+    rem = modExpr(v.getAUse(), mod) and
+    (
+      testIsTrue = polarity and val = r
       or
-      e.(SemShiftLeftExpr).getRightOperand() = c and factor = 2.pow(k) and k > 0
-      or
-      e.(SemBitAndExpr).getAnOperand() = c and factor = max(int f | andmaskFactor(k, f))
+      testIsTrue = polarity.booleanNot() and
+      mod = 2 and
+      val = 1 - r and
+      (r = 0 or r = 1)
     )
-  }
+  )
+}
 
-  /**
-   * Holds if `rix` is the number of input edges to `phi`.
-   */
-  private predicate maxPhiInputRank(SemSsaPhiNode phi, int rix) {
-    rix = max(int r | rankedPhiInput(phi, _, _, r))
-  }
+/**
+ * Holds if a guard ensures that `v` at `pos` is congruent with `val` modulo `mod`.
+ */
+private predicate moduloGuardedRead(SemSsaVariable v, SemSsaReadPosition pos, int val, int mod) {
+  exists(SemGuard guard, boolean testIsTrue |
+    pos.hasReadOfVar(v) and
+    guard = moduloCheck(v, val, mod, testIsTrue) and
+    semGuardControlsSsaRead(guard, pos, testIsTrue)
+  )
+}
 
-  /**
-   * Gets the remainder of `val` modulo `mod`.
-   *
-   * For `mod = 0` the result equals `val` and for `mod > 1` the result is within
-   * the range `[0 .. mod-1]`.
-   */
-  bindingset[val, mod]
-  private int remainder(int val, int mod) {
-    mod = 0 and result = val
+/** Holds if `factor` is a power of 2 that divides `mask`. */
+bindingset[mask]
+private predicate andmaskFactor(int mask, int factor) {
+  mask % factor = 0 and
+  factor = 2.pow([1 .. 30])
+}
+
+/** Holds if `e` is evenly divisible by `factor`. */
+private predicate evenlyDivisibleExpr(SemExpr e, int factor) {
+  exists(SemConstantIntegerExpr c, int k | k = c.getIntValue() |
+    e.(SemMulExpr).getAnOperand() = c and factor = k.abs() and factor >= 2
     or
-    mod > 1 and result = ((val % mod) + mod) % mod
-  }
+    e.(SemShiftLeftExpr).getRightOperand() = c and factor = 2.pow(k) and k > 0
+    or
+    e.(SemBitAndExpr).getAnOperand() = c and factor = max(int f | andmaskFactor(k, f))
+  )
+}
 
-  /**
-   * Holds if `inp` is an input to `phi` and equals `phi` modulo `mod` along `edge`.
-   */
-  private predicate phiSelfModulus(
-    SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int mod
-  ) {
-    exists(Bounds::SemSsaBound phibound, int v, int m |
-      edge.phiInput(phi, inp) and
-      phibound.getAVariable() = phi and
-      ssaModulus(inp, edge, phibound, v, m) and
-      mod = m.gcd(v) and
-      mod != 1
-    )
-  }
+/**
+ * Holds if `rix` is the number of input edges to `phi`.
+ */
+private predicate maxPhiInputRank(SemSsaPhiNode phi, int rix) {
+  rix = max(int r | rankedPhiInput(phi, _, _, r))
+}
 
-  /**
-   * Holds if `b + val` modulo `mod` is a candidate congruence class for `phi`.
-   */
-  private predicate phiModulusInit(SemSsaPhiNode phi, Bounds::SemBound b, int val, int mod) {
-    exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge |
-      edge.phiInput(phi, inp) and
-      ssaModulus(inp, edge, b, val, mod)
-    )
-  }
+/**
+ * Gets the remainder of `val` modulo `mod`.
+ *
+ * For `mod = 0` the result equals `val` and for `mod > 1` the result is within
+ * the range `[0 .. mod-1]`.
+ */
+bindingset[val, mod]
+private int remainder(int val, int mod) {
+  mod = 0 and result = val
+  or
+  mod > 1 and result = ((val % mod) + mod) % mod
+}
 
-  /**
-   * Holds if all inputs to `phi` numbered `1` to `rix` are equal to `b + val` modulo `mod`.
+/**
+ * Holds if `inp` is an input to `phi` and equals `phi` modulo `mod` along `edge`.
+ */
+private predicate phiSelfModulus(
+  SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int mod
+) {
+  exists(SemSsaBound phibound, int v, int m |
+    edge.phiInput(phi, inp) and
+    phibound.getAVariable() = phi and
+    ssaModulus(inp, edge, phibound, v, m) and
+    mod = m.gcd(v) and
+    mod != 1
+  )
+}
+
+/**
+ * Holds if `b + val` modulo `mod` is a candidate congruence class for `phi`.
+ */
+private predicate phiModulusInit(SemSsaPhiNode phi, SemBound b, int val, int mod) {
+  exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge |
+    edge.phiInput(phi, inp) and
+    ssaModulus(inp, edge, b, val, mod)
+  )
+}
+
+/**
+ * Holds if all inputs to `phi` numbered `1` to `rix` are equal to `b + val` modulo `mod`.
+ */
+pragma[nomagic]
+private predicate phiModulusRankStep(SemSsaPhiNode phi, SemBound b, int val, int mod, int rix) {
+  /*
+   * base case. If any phi input is equal to `b + val` modulo `mod`, that's a potential congruence
+   * class for the phi node.
    */
-  pragma[nomagic]
-  private predicate phiModulusRankStep(
-    SemSsaPhiNode phi, Bounds::SemBound b, int val, int mod, int rix
-  ) {
+
+  rix = 0 and
+  phiModulusInit(phi, b, val, mod)
+  or
+  exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int v1, int m1 |
+    mod != 1 and
+    val = remainder(v1, mod)
+  |
     /*
-     * base case. If any phi input is equal to `b + val` modulo `mod`, that's a potential congruence
-     * class for the phi node.
+     * Recursive case. If `inp` = `b + v2` mod `m2`, we combine that with the preceding potential
+     * congruence class `b + v1` mod `m1`. The result will be the congruence class of `v1` modulo
+     * the greatest common denominator of `m1`, `m2`, and `v1 - v2`.
      */
 
-    rix = 0 and
-    phiModulusInit(phi, b, val, mod)
-    or
-    exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int v1, int m1 |
-      mod != 1 and
-      val = remainder(v1, mod)
-    |
-      /*
-       * Recursive case. If `inp` = `b + v2` mod `m2`, we combine that with the preceding potential
-       * congruence class `b + v1` mod `m1`. The result will be the congruence class of `v1` modulo
-       * the greatest common denominator of `m1`, `m2`, and `v1 - v2`.
-       */
-
-      exists(int v2, int m2 |
-        rankedPhiInput(pragma[only_bind_out](phi), inp, edge, rix) and
-        phiModulusRankStep(phi, b, v1, m1, rix - 1) and
-        ssaModulus(inp, edge, b, v2, m2) and
-        mod = m1.gcd(m2).gcd(v1 - v2)
-      )
-      or
-      /*
-       * Recursive case. If `inp` = `phi` mod `m2`, we combine that with the preceding potential
-       * congruence class `b + v1` mod `m1`. The result will be a congruence class modulo the greatest
-       * common denominator of `m1` and `m2`.
-       */
-
-      exists(int m2 |
-        rankedPhiInput(phi, inp, edge, rix) and
-        phiModulusRankStep(phi, b, v1, m1, rix - 1) and
-        phiSelfModulus(phi, inp, edge, m2) and
-        mod = m1.gcd(m2)
-      )
+    exists(int v2, int m2 |
+      rankedPhiInput(pragma[only_bind_out](phi), inp, edge, rix) and
+      phiModulusRankStep(phi, b, v1, m1, rix - 1) and
+      ssaModulus(inp, edge, b, v2, m2) and
+      mod = m1.gcd(m2).gcd(v1 - v2)
     )
-  }
+    or
+    /*
+     * Recursive case. If `inp` = `phi` mod `m2`, we combine that with the preceding potential
+     * congruence class `b + v1` mod `m1`. The result will be a congruence class modulo the greatest
+     * common denominator of `m1` and `m2`.
+     */
 
-  /**
-   * Holds if `phi` is equal to `b + val` modulo `mod`.
-   */
-  private predicate phiModulus(SemSsaPhiNode phi, Bounds::SemBound b, int val, int mod) {
-    exists(int r |
-      maxPhiInputRank(phi, r) and
-      phiModulusRankStep(phi, b, val, mod, r)
+    exists(int m2 |
+      rankedPhiInput(phi, inp, edge, rix) and
+      phiModulusRankStep(phi, b, v1, m1, rix - 1) and
+      phiSelfModulus(phi, inp, edge, m2) and
+      mod = m1.gcd(m2)
     )
-  }
+  )
+}
 
-  /**
-   * Holds if `v` at `pos` is equal to `b + val` modulo `mod`.
-   */
-  private predicate ssaModulus(
-    SemSsaVariable v, SemSsaReadPosition pos, Bounds::SemBound b, int val, int mod
-  ) {
-    phiModulus(v, b, val, mod) and pos.hasReadOfVar(v)
+/**
+ * Holds if `phi` is equal to `b + val` modulo `mod`.
+ */
+private predicate phiModulus(SemSsaPhiNode phi, SemBound b, int val, int mod) {
+  exists(int r |
+    maxPhiInputRank(phi, r) and
+    phiModulusRankStep(phi, b, val, mod, r)
+  )
+}
+
+/**
+ * Holds if `v` at `pos` is equal to `b + val` modulo `mod`.
+ */
+private predicate ssaModulus(SemSsaVariable v, SemSsaReadPosition pos, SemBound b, int val, int mod) {
+  phiModulus(v, b, val, mod) and pos.hasReadOfVar(v)
+  or
+  b.(SemSsaBound).getAVariable() = v and pos.hasReadOfVar(v) and val = 0 and mod = 0
+  or
+  exists(SemExpr e, int val0, int delta |
+    semExprModulus(e, b, val0, mod) and
+    valueFlowStepSsa(v, pos, e, delta) and
+    val = remainder(val0 + delta, mod)
+  )
+  or
+  moduloGuardedRead(v, pos, val, mod) and b instanceof SemZeroBound
+}
+
+/**
+ * Holds if `e` is equal to `b + val` modulo `mod`.
+ *
+ * There are two cases for the modulus:
+ * - `mod = 0`: The equality `e = b + val` is an ordinary equality.
+ * - `mod > 1`: `val` lies within the range `[0 .. mod-1]`.
+ */
+cached
+predicate semExprModulus(SemExpr e, SemBound b, int val, int mod) {
+  not ignoreExprModulus(e) and
+  (
+    e = b.getExpr(val) and mod = 0
     or
-    b.(Bounds::SemSsaBound).getAVariable() = v and pos.hasReadOfVar(v) and val = 0 and mod = 0
+    evenlyDivisibleExpr(e, mod) and
+    val = 0 and
+    b instanceof SemZeroBound
     or
-    exists(SemExpr e, int val0, int delta |
-      semExprModulus(e, b, val0, mod) and
-      valueFlowStepSsa(v, pos, e, delta) and
+    exists(SemSsaVariable v, SemSsaReadPositionBlock bb |
+      ssaModulus(v, bb, b, val, mod) and
+      e = v.getAUse() and
+      bb.getAnExpr() = e
+    )
+    or
+    exists(SemExpr mid, int val0, int delta |
+      semExprModulus(mid, b, val0, mod) and
+      semValueFlowStep(e, mid, delta) and
       val = remainder(val0 + delta, mod)
     )
     or
-    moduloGuardedRead(v, pos, val, mod) and b instanceof Bounds::SemZeroBound
-  }
-
-  /**
-   * Holds if `e` is equal to `b + val` modulo `mod`.
-   *
-   * There are two cases for the modulus:
-   * - `mod = 0`: The equality `e = b + val` is an ordinary equality.
-   * - `mod > 1`: `val` lies within the range `[0 .. mod-1]`.
-   */
-  cached
-  predicate semExprModulus(SemExpr e, Bounds::SemBound b, int val, int mod) {
-    not ignoreExprModulus(e) and
-    (
-      e = b.getExpr(D::fromInt(val)) and mod = 0
-      or
-      evenlyDivisibleExpr(e, mod) and
-      val = 0 and
-      b instanceof Bounds::SemZeroBound
-      or
-      exists(SemSsaVariable v, SemSsaReadPositionBlock bb |
-        ssaModulus(v, bb, b, val, mod) and
-        e = v.getAUse() and
-        bb.getAnExpr() = e
-      )
-      or
-      exists(SemExpr mid, int val0, int delta |
-        semExprModulus(mid, b, val0, mod) and
-        U::semValueFlowStep(e, mid, D::fromInt(delta)) and
-        val = remainder(val0 + delta, mod)
-      )
-      or
-      exists(SemConditionalExpr cond, int v1, int v2, int m1, int m2 |
-        cond = e and
-        condExprBranchModulus(cond, true, b, v1, m1) and
-        condExprBranchModulus(cond, false, b, v2, m2) and
-        mod = m1.gcd(m2).gcd(v1 - v2) and
-        mod != 1 and
-        val = remainder(v1, mod)
-      )
-      or
-      exists(Bounds::SemBound b1, Bounds::SemBound b2, int v1, int v2, int m1, int m2 |
-        addModulus(e, true, b1, v1, m1) and
-        addModulus(e, false, b2, v2, m2) and
-        mod = m1.gcd(m2) and
-        mod != 1 and
-        val = remainder(v1 + v2, mod)
-      |
-        b = b1 and b2 instanceof Bounds::SemZeroBound
-        or
-        b = b2 and b1 instanceof Bounds::SemZeroBound
-      )
-      or
-      exists(int v1, int v2, int m1, int m2 |
-        subModulus(e, true, b, v1, m1) and
-        subModulus(e, false, any(Bounds::SemZeroBound zb), v2, m2) and
-        mod = m1.gcd(m2) and
-        mod != 1 and
-        val = remainder(v1 - v2, mod)
-      )
+    exists(SemConditionalExpr cond, int v1, int v2, int m1, int m2 |
+      cond = e and
+      condExprBranchModulus(cond, true, b, v1, m1) and
+      condExprBranchModulus(cond, false, b, v2, m2) and
+      mod = m1.gcd(m2).gcd(v1 - v2) and
+      mod != 1 and
+      val = remainder(v1, mod)
     )
-  }
-
-  private predicate condExprBranchModulus(
-    SemConditionalExpr cond, boolean branch, Bounds::SemBound b, int val, int mod
-  ) {
-    semExprModulus(cond.getBranchExpr(branch), b, val, mod)
-  }
-
-  private predicate addModulus(SemExpr add, boolean isLeft, Bounds::SemBound b, int val, int mod) {
-    exists(SemExpr larg, SemExpr rarg | nonConstAddition(add, larg, rarg) |
-      semExprModulus(larg, b, val, mod) and isLeft = true
+    or
+    exists(SemBound b1, SemBound b2, int v1, int v2, int m1, int m2 |
+      addModulus(e, true, b1, v1, m1) and
+      addModulus(e, false, b2, v2, m2) and
+      mod = m1.gcd(m2) and
+      mod != 1 and
+      val = remainder(v1 + v2, mod)
+    |
+      b = b1 and b2 instanceof SemZeroBound
       or
-      semExprModulus(rarg, b, val, mod) and isLeft = false
+      b = b2 and b1 instanceof SemZeroBound
     )
-  }
-
-  private predicate subModulus(SemExpr sub, boolean isLeft, Bounds::SemBound b, int val, int mod) {
-    exists(SemExpr larg, SemExpr rarg | nonConstSubtraction(sub, larg, rarg) |
-      semExprModulus(larg, b, val, mod) and isLeft = true
-      or
-      semExprModulus(rarg, b, val, mod) and isLeft = false
+    or
+    exists(int v1, int v2, int m1, int m2 |
+      subModulus(e, true, b, v1, m1) and
+      subModulus(e, false, any(SemZeroBound zb), v2, m2) and
+      mod = m1.gcd(m2) and
+      mod != 1 and
+      val = remainder(v1 - v2, mod)
+    )
+  )
+}
+
+private predicate condExprBranchModulus(
+  SemConditionalExpr cond, boolean branch, SemBound b, int val, int mod
+) {
+  semExprModulus(cond.getBranchExpr(branch), b, val, mod)
+}
+
+private predicate addModulus(SemExpr add, boolean isLeft, SemBound b, int val, int mod) {
+  exists(SemExpr larg, SemExpr rarg | nonConstAddition(add, larg, rarg) |
+    semExprModulus(larg, b, val, mod) and isLeft = true
+    or
+    semExprModulus(rarg, b, val, mod) and isLeft = false
+  )
+}
+
+private predicate subModulus(SemExpr sub, boolean isLeft, SemBound b, int val, int mod) {
+  exists(SemExpr larg, SemExpr rarg | nonConstSubtraction(sub, larg, rarg) |
+    semExprModulus(larg, b, val, mod) and isLeft = true
+    or
+    semExprModulus(rarg, b, val, mod) and isLeft = false
+  )
+}
+
+/**
+ * Holds if `inp` is an input to `phi` along `edge` and this input has index `r`
+ * in an arbitrary 1-based numbering of the input edges to `phi`.
+ */
+private predicate rankedPhiInput(
+  SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int r
+) {
+  edge.phiInput(phi, inp) and
+  edge =
+    rank[r](SemSsaReadPositionPhiInputEdge e |
+      e.phiInput(phi, _)
+    |
+      e order by e.getOrigBlock().getUniqueId()
     )
-  }
-
-  /**
-   * Holds if `inp` is an input to `phi` along `edge` and this input has index `r`
-   * in an arbitrary 1-based numbering of the input edges to `phi`.
-   */
-  private predicate rankedPhiInput(
-    SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int r
-  ) {
-    edge.phiInput(phi, inp) and
-    edge =
-      rank[r](SemSsaReadPositionPhiInputEdge e |
-        e.phiInput(phi, _)
-      |
-        e order by e.getOrigBlock().getUniqueId()
-      )
-  }
 }

cpp/ql/lib/experimental/semmle/code/cpp/semantic/analysis/RangeAnalysis.qll

@@ -1,24 +1,832 @@
-private import RangeAnalysisStage
-private import RangeAnalysisSpecific
-private import experimental.semmle.code.cpp.semantic.analysis.FloatDelta
+/**
+ * Provides classes and predicates for range analysis.
+ *
+ * An inferred bound can either be a specific integer, the abstract value of an
+ * SSA variable, or the abstract value of an interesting expression. The latter
+ * category includes array lengths that are not SSA variables.
+ *
+ * If an inferred bound relies directly on a condition, then this condition is
+ * reported as the reason for the bound.
+ */
+
+/*
+ * This library tackles range analysis as a flow problem. Consider e.g.:
+ * ```
+ *   len = arr.length;
+ *   if (x < len) { ... y = x-1; ... y ... }
+ * ```
+ * In this case we would like to infer `y <= arr.length - 2`, and this is
+ * accomplished by tracking the bound through a sequence of steps:
+ * ```
+ *   arr.length --> len = .. --> x < len --> x-1 --> y = .. --> y
+ * ```
+ *
+ * In its simplest form the step relation `E1 --> E2` relates two expressions
+ * such that `E1 <= B` implies `E2 <= B` for any `B` (with a second separate
+ * step relation handling lower bounds). Examples of such steps include
+ * assignments `E2 = E1` and conditions `x <= E1` where `E2` is a use of `x`
+ * guarded by the condition.
+ *
+ * In order to handle subtractions and additions with constants, and strict
+ * comparisons, the step relation is augmented with an integer delta. With this
+ * generalization `E1 --(delta)--> E2` relates two expressions and an integer
+ * such that `E1 <= B` implies `E2 <= B + delta` for any `B`. This corresponds
+ * to the predicate `boundFlowStep`.
+ *
+ * The complete range analysis is then implemented as the transitive closure of
+ * the step relation summing the deltas along the way. If `E1` transitively
+ * steps to `E2`, `delta` is the sum of deltas along the path, and `B` is an
+ * interesting bound equal to the value of `E1` then `E2 <= B + delta`. This
+ * corresponds to the predicate `bounded`.
+ *
+ * Phi nodes need a little bit of extra handling. Consider `x0 = phi(x1, x2)`.
+ * There are essentially two cases:
+ * - If `x1 <= B + d1` and `x2 <= B + d2` then `x0 <= B + max(d1,d2)`.
+ * - If `x1 <= B + d1` and `x2 <= x0 + d2` with `d2 <= 0` then `x0 <= B + d1`.
+ * The first case is for whenever a bound can be proven without taking looping
+ * into account. The second case is relevant when `x2` comes from a back-edge
+ * where we can prove that the variable has been non-increasing through the
+ * loop-iteration as this means that any upper bound that holds prior to the
+ * loop also holds for the variable during the loop.
+ * This generalizes to a phi node with `n` inputs, so if
+ * `x0 = phi(x1, ..., xn)` and `xi <= B + delta` for one of the inputs, then we
+ * also have `x0 <= B + delta` if we can prove either:
+ * - `xj <= B + d` with `d <= delta` or
+ * - `xj <= x0 + d` with `d <= 0`
+ * for each input `xj`.
+ *
+ * As all inferred bounds can be related directly to a path in the source code
+ * the only source of non-termination is if successive redundant (and thereby
+ * increasingly worse) bounds are calculated along a loop in the source code.
+ * We prevent this by weakening the bound to a small finite set of bounds when
+ * a path follows a second back-edge (we postpone weakening till the second
+ * back-edge as a precise bound might require traversing a loop once).
+ */
+
+private import RangeAnalysisSpecific as Specific
 private import RangeUtils
-private import experimental.semmle.code.cpp.semantic.SemanticBound as SemanticBound
+private import SignAnalysisCommon
+private import ModulusAnalysis
+private import experimental.semmle.code.cpp.semantic.Semantic
+private import ConstantAnalysis
 
-module Bounds implements BoundSig<FloatDelta> {
-  class SemBound instanceof SemanticBound::SemBound {
-    string toString() { result = super.toString() }
-
-    SemExpr getExpr(float delta) { result = super.getExpr(delta) }
+cached
+private module RangeAnalysisCache {
+  cached
+  module RangeAnalysisPublic {
+    /**
+     * Holds if `b + delta` is a valid bound for `e`.
+     * - `upper = true`  : `e <= b + delta`
+     * - `upper = false` : `e >= b + delta`
+     *
+     * The reason for the bound is given by `reason` and may be either a condition
+     * or `NoReason` if the bound was proven directly without the use of a bounding
+     * condition.
+     */
+    cached
+    predicate semBounded(SemExpr e, SemBound b, int delta, boolean upper, SemReason reason) {
+      bounded(e, b, delta, upper, _, _, reason) and
+      bestBound(e, b, delta, upper)
+    }
   }
 
-  class SemZeroBound extends SemBound instanceof SemanticBound::SemZeroBound { }
-
-  class SemSsaBound extends SemBound instanceof SemanticBound::SemSsaBound {
-    SemSsaVariable getAVariable() { result = this.(SemanticBound::SemSsaBound).getAVariable() }
+  /**
+   * Holds if `guard = boundFlowCond(_, _, _, _, _) or guard = eqFlowCond(_, _, _, _, _)`.
+   */
+  cached
+  predicate possibleReason(SemGuard guard) {
+    guard = boundFlowCond(_, _, _, _, _) or guard = semEqFlowCond(_, _, _, _, _)
   }
 }
 
-private module CppRangeAnalysis =
-  RangeStage<FloatDelta, Bounds, CppLangImpl, RangeUtil<FloatDelta, CppLangImpl>>;
+private import RangeAnalysisCache
+import RangeAnalysisPublic
 
-import CppRangeAnalysis
+/**
+ * Holds if `b + delta` is a valid bound for `e` and this is the best such delta.
+ * - `upper = true`  : `e <= b + delta`
+ * - `upper = false` : `e >= b + delta`
+ */
+private predicate bestBound(SemExpr e, SemBound b, int delta, boolean upper) {
+  delta = min(int d | bounded(e, b, d, upper, _, _, _)) and upper = true
+  or
+  delta = max(int d | bounded(e, b, d, upper, _, _, _)) and upper = false
+}
+
+/**
+ * Holds if `comp` corresponds to:
+ * - `upper = true`  : `v <= e + delta` or `v < e + delta`
+ * - `upper = false` : `v >= e + delta` or `v > e + delta`
+ */
+private predicate boundCondition(
+  SemRelationalExpr comp, SemSsaVariable v, SemExpr e, int delta, boolean upper
+) {
+  comp.getLesserOperand() = semSsaRead(v, delta) and e = comp.getGreaterOperand() and upper = true
+  or
+  comp.getGreaterOperand() = semSsaRead(v, delta) and e = comp.getLesserOperand() and upper = false
+  or
+  exists(SemSubExpr sub, SemConstantIntegerExpr c, int d |
+    // (v - d) - e < c
+    comp.getLesserOperand() = sub and
+    comp.getGreaterOperand() = c and
+    sub.getLeftOperand() = semSsaRead(v, d) and
+    sub.getRightOperand() = e and
+    upper = true and
+    delta = d + c.getIntValue()
+    or
+    // (v - d) - e > c
+    comp.getGreaterOperand() = sub and
+    comp.getLesserOperand() = c and
+    sub.getLeftOperand() = semSsaRead(v, d) and
+    sub.getRightOperand() = e and
+    upper = false and
+    delta = d + c.getIntValue()
+    or
+    // e - (v - d) < c
+    comp.getLesserOperand() = sub and
+    comp.getGreaterOperand() = c and
+    sub.getLeftOperand() = e and
+    sub.getRightOperand() = semSsaRead(v, d) and
+    upper = false and
+    delta = d - c.getIntValue()
+    or
+    // e - (v - d) > c
+    comp.getGreaterOperand() = sub and
+    comp.getLesserOperand() = c and
+    sub.getLeftOperand() = e and
+    sub.getRightOperand() = semSsaRead(v, d) and
+    upper = true and
+    delta = d - c.getIntValue()
+  )
+}
+
+/**
+ * Holds if `comp` is a comparison between `x` and `y` for which `y - x` has a
+ * fixed value modulo some `mod > 1`, such that the comparison can be
+ * strengthened by `strengthen` when evaluating to `testIsTrue`.
+ */
+private predicate modulusComparison(SemRelationalExpr comp, boolean testIsTrue, int strengthen) {
+  exists(
+    SemBound b, int v1, int v2, int mod1, int mod2, int mod, boolean resultIsStrict, int d, int k
+  |
+    // If `x <= y` and `x =(mod) b + v1` and `y =(mod) b + v2` then
+    // `0 <= y - x =(mod) v2 - v1`. By choosing `k =(mod) v2 - v1` with
+    // `0 <= k < mod` we get `k <= y - x`. If the resulting comparison is
+    // strict then the strengthening amount is instead `k - 1` modulo `mod`:
+    // `x < y` means `0 <= y - x - 1 =(mod) k - 1` so `k - 1 <= y - x - 1` and
+    // thus `k - 1 < y - x` with `0 <= k - 1 < mod`.
+    semExprModulus(comp.getLesserOperand(), b, v1, mod1) and
+    semExprModulus(comp.getGreaterOperand(), b, v2, mod2) and
+    mod = mod1.gcd(mod2) and
+    mod != 1 and
+    (testIsTrue = true or testIsTrue = false) and
+    (
+      if comp.isStrict()
+      then resultIsStrict = testIsTrue
+      else resultIsStrict = testIsTrue.booleanNot()
+    ) and
+    (
+      resultIsStrict = true and d = 1
+      or
+      resultIsStrict = false and d = 0
+    ) and
+    (
+      testIsTrue = true and k = v2 - v1
+      or
+      testIsTrue = false and k = v1 - v2
+    ) and
+    strengthen = (((k - d) % mod) + mod) % mod
+  )
+}
+
+/**
+ * Gets a condition that tests whether `v` is bounded by `e + delta`.
+ *
+ * If the condition evaluates to `testIsTrue`:
+ * - `upper = true`  : `v <= e + delta`
+ * - `upper = false` : `v >= e + delta`
+ */
+private SemGuard boundFlowCond(
+  SemSsaVariable v, SemExpr e, int delta, boolean upper, boolean testIsTrue
+) {
+  exists(
+    SemRelationalExpr comp, int d1, int d2, int d3, int strengthen, boolean compIsUpper,
+    boolean resultIsStrict
+  |
+    comp = result.asExpr() and
+    boundCondition(comp, v, e, d1, compIsUpper) and
+    (testIsTrue = true or testIsTrue = false) and
+    upper = compIsUpper.booleanXor(testIsTrue.booleanNot()) and
+    (
+      if comp.isStrict()
+      then resultIsStrict = testIsTrue
+      else resultIsStrict = testIsTrue.booleanNot()
+    ) and
+    (
+      if
+        getTrackedTypeForSsaVariable(v) instanceof SemIntegerType or
+        getTrackedTypeForSsaVariable(v) instanceof SemAddressType
+      then
+        upper = true and strengthen = -1
+        or
+        upper = false and strengthen = 1
+      else strengthen = 0
+    ) and
+    (
+      exists(int k | modulusComparison(comp, testIsTrue, k) and d2 = strengthen * k)
+      or
+      not modulusComparison(comp, testIsTrue, _) and d2 = 0
+    ) and
+    // A strict inequality `x < y` can be strengthened to `x <= y - 1`.
+    (
+      resultIsStrict = true and d3 = strengthen
+      or
+      resultIsStrict = false and d3 = 0
+    ) and
+    delta = d1 + d2 + d3
+  )
+  or
+  exists(boolean testIsTrue0 |
+    semImplies_v2(result, testIsTrue, boundFlowCond(v, e, delta, upper, testIsTrue0), testIsTrue0)
+  )
+  or
+  result = semEqFlowCond(v, e, delta, true, testIsTrue) and
+  (upper = true or upper = false)
+  or
+  // guard that tests whether `v2` is bounded by `e + delta + d1 - d2` and
+  // exists a guard `guardEq` such that `v = v2 - d1 + d2`.
+  exists(SemSsaVariable v2, SemGuard guardEq, boolean eqIsTrue, int d1, int d2 |
+    guardEq = semEqFlowCond(v, semSsaRead(v2, d1), d2, true, eqIsTrue) and
+    result = boundFlowCond(v2, e, delta + d1 - d2, upper, testIsTrue) and
+    // guardEq needs to control guard
+    guardEq.directlyControls(result.getBasicBlock(), eqIsTrue)
+  )
+}
+
+private newtype TSemReason =
+  TSemNoReason() or
+  TSemCondReason(SemGuard guard) { possibleReason(guard) }
+
+/**
+ * A reason for an inferred bound. This can either be `CondReason` if the bound
+ * is due to a specific condition, or `NoReason` if the bound is inferred
+ * without going through a bounding condition.
+ */
+abstract class SemReason extends TSemReason {
+  /** Gets a textual representation of this reason. */
+  abstract string toString();
+}
+
+/**
+ * A reason for an inferred bound that indicates that the bound is inferred
+ * without going through a bounding condition.
+ */
+class SemNoReason extends SemReason, TSemNoReason {
+  override string toString() { result = "NoReason" }
+}
+
+/** A reason for an inferred bound pointing to a condition. */
+class SemCondReason extends SemReason, TSemCondReason {
+  /** Gets the condition that is the reason for the bound. */
+  SemGuard getCond() { this = TSemCondReason(result) }
+
+  override string toString() { result = getCond().toString() }
+}
+
+/**
+ * Holds if `e + delta` is a valid bound for `v` at `pos`.
+ * - `upper = true`  : `v <= e + delta`
+ * - `upper = false` : `v >= e + delta`
+ */
+private predicate boundFlowStepSsa(
+  SemSsaVariable v, SemSsaReadPosition pos, SemExpr e, int delta, boolean upper, SemReason reason
+) {
+  semSsaUpdateStep(v, e, delta) and
+  pos.hasReadOfVar(v) and
+  (upper = true or upper = false) and
+  reason = TSemNoReason()
+  or
+  exists(SemGuard guard, boolean testIsTrue |
+    pos.hasReadOfVar(v) and
+    guard = boundFlowCond(v, e, delta, upper, testIsTrue) and
+    semGuardDirectlyControlsSsaRead(guard, pos, testIsTrue) and
+    reason = TSemCondReason(guard)
+  )
+}
+
+/** Holds if `v != e + delta` at `pos` and `v` is of integral type. */
+private predicate unequalFlowStepIntegralSsa(
+  SemSsaVariable v, SemSsaReadPosition pos, SemExpr e, int delta, SemReason reason
+) {
+  getTrackedTypeForSsaVariable(v) instanceof SemIntegerType and
+  exists(SemGuard guard, boolean testIsTrue |
+    pos.hasReadOfVar(v) and
+    guard = semEqFlowCond(v, e, delta, false, testIsTrue) and
+    semGuardDirectlyControlsSsaRead(guard, pos, testIsTrue) and
+    reason = TSemCondReason(guard)
+  )
+}
+
+/**
+ * An expression that does conversion, boxing, or unboxing
+ */
+private class ConvertOrBoxExpr extends SemUnaryExpr {
+  ConvertOrBoxExpr() {
+    this instanceof SemConvertExpr
+    or
+    this instanceof SemBoxExpr
+    or
+    this instanceof SemUnboxExpr
+  }
+}
+
+/**
+ * A cast that can be ignored for the purpose of range analysis.
+ */
+private class SafeCastExpr extends ConvertOrBoxExpr {
+  SafeCastExpr() {
+    conversionCannotOverflow(getTrackedType(pragma[only_bind_into](getOperand())),
+      getTrackedType(this))
+  }
+}
+
+/**
+ * Holds if `typ` is a small integral type with the given lower and upper bounds.
+ */
+private predicate typeBound(SemIntegerType typ, int lowerbound, int upperbound) {
+  exists(int bitSize | bitSize = typ.getByteSize() * 8 |
+    bitSize < 32 and
+    (
+      if typ.isSigned()
+      then (
+        upperbound = 1.bitShiftLeft(bitSize - 1) - 1 and
+        lowerbound = -upperbound - 1
+      ) else (
+        lowerbound = 0 and
+        upperbound = 1.bitShiftLeft(bitSize) - 1
+      )
+    )
+  )
+}
+
+/**
+ * A cast to a small integral type that may overflow or underflow.
+ */
+private class NarrowingCastExpr extends ConvertOrBoxExpr {
+  NarrowingCastExpr() {
+    not this instanceof SafeCastExpr and
+    typeBound(getTrackedType(this), _, _)
+  }
+
+  /** Gets the lower bound of the resulting type. */
+  int getLowerBound() { typeBound(getTrackedType(this), result, _) }
+
+  /** Gets the upper bound of the resulting type. */
+  int getUpperBound() { typeBound(getTrackedType(this), _, result) }
+}
+
+/** Holds if `e >= 1` as determined by sign analysis. */
+private predicate strictlyPositiveIntegralExpr(SemExpr e) {
+  semStrictlyPositive(e) and getTrackedType(e) instanceof SemIntegerType
+}
+
+/** Holds if `e <= -1` as determined by sign analysis. */
+private predicate strictlyNegativeIntegralExpr(SemExpr e) {
+  semStrictlyNegative(e) and getTrackedType(e) instanceof SemIntegerType
+}
+
+/**
+ * Holds if `e1 + delta` is a valid bound for `e2`.
+ * - `upper = true`  : `e2 <= e1 + delta`
+ * - `upper = false` : `e2 >= e1 + delta`
+ */
+private predicate boundFlowStep(SemExpr e2, SemExpr e1, int delta, boolean upper) {
+  semValueFlowStep(e2, e1, delta) and
+  (upper = true or upper = false)
+  or
+  e2.(SafeCastExpr).getOperand() = e1 and
+  delta = 0 and
+  (upper = true or upper = false)
+  or
+  exists(SemExpr x | e2.(SemAddExpr).hasOperands(e1, x) |
+    // `x instanceof ConstantIntegerExpr` is covered by valueFlowStep
+    not x instanceof SemConstantIntegerExpr and
+    not e1 instanceof SemConstantIntegerExpr and
+    if strictlyPositiveIntegralExpr(x)
+    then upper = false and delta = 1
+    else
+      if semPositive(x)
+      then upper = false and delta = 0
+      else
+        if strictlyNegativeIntegralExpr(x)
+        then upper = true and delta = -1
+        else
+          if semNegative(x)
+          then upper = true and delta = 0
+          else none()
+  )
+  or
+  exists(SemExpr x, SemSubExpr sub |
+    e2 = sub and
+    sub.getLeftOperand() = e1 and
+    sub.getRightOperand() = x
+  |
+    // `x instanceof ConstantIntegerExpr` is covered by valueFlowStep
+    not x instanceof SemConstantIntegerExpr and
+    if strictlyPositiveIntegralExpr(x)
+    then upper = true and delta = -1
+    else
+      if semPositive(x)
+      then upper = true and delta = 0
+      else
+        if strictlyNegativeIntegralExpr(x)
+        then upper = false and delta = 1
+        else
+          if semNegative(x)
+          then upper = false and delta = 0
+          else none()
+  )
+  or
+  e2.(SemRemExpr).getRightOperand() = e1 and
+  semPositive(e1) and
+  delta = -1 and
+  upper = true
+  or
+  e2.(SemRemExpr).getLeftOperand() = e1 and semPositive(e1) and delta = 0 and upper = true
+  or
+  e2.(SemBitAndExpr).getAnOperand() = e1 and
+  semPositive(e1) and
+  delta = 0 and
+  upper = true
+  or
+  e2.(SemBitOrExpr).getAnOperand() = e1 and
+  semPositive(e2) and
+  delta = 0 and
+  upper = false
+  or
+  Specific::hasBound(e2, e1, delta, upper)
+}
+
+/** Holds if `e2 = e1 * factor` and `factor > 0`. */
+private predicate boundFlowStepMul(SemExpr e2, SemExpr e1, int factor) {
+  exists(SemConstantIntegerExpr c, int k | k = c.getIntValue() and k > 0 |
+    e2.(SemMulExpr).hasOperands(e1, c) and factor = k
+    or
+    exists(SemShiftLeftExpr e |
+      e = e2 and e.getLeftOperand() = e1 and e.getRightOperand() = c and factor = 2.pow(k)
+    )
+  )
+}
+
+/**
+ * Holds if `e2 = e1 / factor` and `factor > 0`.
+ *
+ * This conflates division, right shift, and unsigned right shift and is
+ * therefore only valid for non-negative numbers.
+ */
+private predicate boundFlowStepDiv(SemExpr e2, SemExpr e1, int factor) {
+  exists(SemConstantIntegerExpr c, int k | k = c.getIntValue() and k > 0 |
+    exists(SemDivExpr e |
+      e = e2 and e.getLeftOperand() = e1 and e.getRightOperand() = c and factor = k
+    )
+    or
+    exists(SemShiftRightExpr e |
+      e = e2 and e.getLeftOperand() = e1 and e.getRightOperand() = c and factor = 2.pow(k)
+    )
+    or
+    exists(SemShiftRightUnsignedExpr e |
+      e = e2 and e.getLeftOperand() = e1 and e.getRightOperand() = c and factor = 2.pow(k)
+    )
+  )
+}
+
+/**
+ * Holds if `b + delta` is a valid bound for `v` at `pos`.
+ * - `upper = true`  : `v <= b + delta`
+ * - `upper = false` : `v >= b + delta`
+ */
+private predicate boundedSsa(
+  SemSsaVariable v, SemSsaReadPosition pos, SemBound b, int delta, boolean upper,
+  boolean fromBackEdge, int origdelta, SemReason reason
+) {
+  exists(SemExpr mid, int d1, int d2, SemReason r1, SemReason r2 |
+    boundFlowStepSsa(v, pos, mid, d1, upper, r1) and
+    bounded(mid, b, d2, upper, fromBackEdge, origdelta, r2) and
+    // upper = true:  v <= mid + d1 <= b + d1 + d2 = b + delta
+    // upper = false: v >= mid + d1 >= b + d1 + d2 = b + delta
+    delta = d1 + d2 and
+    (if r1 instanceof SemNoReason then reason = r2 else reason = r1)
+  )
+  or
+  exists(int d, SemReason r1, SemReason r2 |
+    boundedSsa(v, pos, b, d, upper, fromBackEdge, origdelta, r2) or
+    boundedPhi(v, b, d, upper, fromBackEdge, origdelta, r2)
+  |
+    unequalIntegralSsa(v, pos, b, d, r1) and
+    (
+      upper = true and delta = d - 1
+      or
+      upper = false and delta = d + 1
+    ) and
+    (
+      reason = r1
+      or
+      reason = r2 and not r2 instanceof SemNoReason
+    )
+  )
+}
+
+/**
+ * Holds if `v != b + delta` at `pos` and `v` is of integral type.
+ */
+private predicate unequalIntegralSsa(
+  SemSsaVariable v, SemSsaReadPosition pos, SemBound b, int delta, SemReason reason
+) {
+  exists(SemExpr e, int d1, int d2 |
+    unequalFlowStepIntegralSsa(v, pos, e, d1, reason) and
+    boundedUpper(e, b, d1) and
+    boundedLower(e, b, d2) and
+    delta = d2 + d1
+  )
+}
+
+/**
+ * Holds if `b + delta` is an upper bound for `e`.
+ *
+ * This predicate only exists to prevent a bad standard order in `unequalIntegralSsa`.
+ */
+pragma[nomagic]
+private predicate boundedUpper(SemExpr e, SemBound b, int delta) {
+  bounded(e, b, delta, true, _, _, _)
+}
+
+/**
+ * Holds if `b + delta` is a lower bound for `e`.
+ *
+ * This predicate only exists to prevent a bad standard order in `unequalIntegralSsa`.
+ */
+pragma[nomagic]
+private predicate boundedLower(SemExpr e, SemBound b, int delta) {
+  bounded(e, b, delta, false, _, _, _)
+}
+
+/** Weakens a delta to lie in the range `[-1..1]`. */
+bindingset[delta, upper]
+private int weakenDelta(boolean upper, int delta) {
+  delta in [-1 .. 1] and result = delta
+  or
+  upper = true and result = -1 and delta < -1
+  or
+  upper = false and result = 1 and delta > 1
+}
+
+/**
+ * Holds if `b + delta` is a valid bound for `inp` when used as an input to
+ * `phi` along `edge`.
+ * - `upper = true`  : `inp <= b + delta`
+ * - `upper = false` : `inp >= b + delta`
+ */
+private predicate boundedPhiInp(
+  SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, SemBound b, int delta,
+  boolean upper, boolean fromBackEdge, int origdelta, SemReason reason
+) {
+  edge.phiInput(phi, inp) and
+  exists(int d, boolean fromBackEdge0 |
+    boundedSsa(inp, edge, b, d, upper, fromBackEdge0, origdelta, reason)
+    or
+    boundedPhi(inp, b, d, upper, fromBackEdge0, origdelta, reason)
+    or
+    b.(SemSsaBound).getAVariable() = inp and
+    d = 0 and
+    (upper = true or upper = false) and
+    fromBackEdge0 = false and
+    origdelta = 0 and
+    reason = TSemNoReason()
+  |
+    if semBackEdge(phi, inp, edge)
+    then
+      fromBackEdge = true and
+      (
+        fromBackEdge0 = true and delta = weakenDelta(upper, d - origdelta) + origdelta
+        or
+        fromBackEdge0 = false and delta = d
+      )
+    else (
+      delta = d and fromBackEdge = fromBackEdge0
+    )
+  )
+}
+
+/**
+ * Holds if `b + delta` is a valid bound for `inp` when used as an input to
+ * `phi` along `edge`.
+ * - `upper = true`  : `inp <= b + delta`
+ * - `upper = false` : `inp >= b + delta`
+ *
+ * Equivalent to `boundedPhiInp(phi, inp, edge, b, delta, upper, _, _, _)`.
+ */
+pragma[noinline]
+private predicate boundedPhiInp1(
+  SemSsaPhiNode phi, SemBound b, boolean upper, SemSsaVariable inp,
+  SemSsaReadPositionPhiInputEdge edge, int delta
+) {
+  boundedPhiInp(phi, inp, edge, b, delta, upper, _, _, _)
+}
+
+/**
+ * Holds if `phi` is a valid bound for `inp` when used as an input to `phi`
+ * along `edge`.
+ * - `upper = true`  : `inp <= phi`
+ * - `upper = false` : `inp >= phi`
+ */
+private predicate selfBoundedPhiInp(
+  SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, boolean upper
+) {
+  exists(int d, SemSsaBound phibound |
+    phibound.getAVariable() = phi and
+    boundedPhiInp(phi, inp, edge, phibound, d, upper, _, _, _) and
+    (
+      upper = true and d <= 0
+      or
+      upper = false and d >= 0
+    )
+  )
+}
+
+/**
+ * Holds if `b + delta` is a valid bound for some input, `inp`, to `phi`, and
+ * thus a candidate bound for `phi`.
+ * - `upper = true`  : `inp <= b + delta`
+ * - `upper = false` : `inp >= b + delta`
+ */
+pragma[noinline]
+private predicate boundedPhiCand(
+  SemSsaPhiNode phi, boolean upper, SemBound b, int delta, boolean fromBackEdge, int origdelta,
+  SemReason reason
+) {
+  exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge |
+    boundedPhiInp(phi, inp, edge, b, delta, upper, fromBackEdge, origdelta, reason)
+  )
+}
+
+/**
+ * Holds if the candidate bound `b + delta` for `phi` is valid for the phi input
+ * `inp` along `edge`.
+ */
+private predicate boundedPhiCandValidForEdge(
+  SemSsaPhiNode phi, SemBound b, int delta, boolean upper, boolean fromBackEdge, int origdelta,
+  SemReason reason, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge
+) {
+  boundedPhiCand(phi, upper, b, delta, fromBackEdge, origdelta, reason) and
+  (
+    exists(int d | boundedPhiInp1(phi, b, upper, inp, edge, d) | upper = true and d <= delta)
+    or
+    exists(int d | boundedPhiInp1(phi, b, upper, inp, edge, d) | upper = false and d >= delta)
+    or
+    selfBoundedPhiInp(phi, inp, edge, upper)
+  )
+}
+
+/**
+ * Holds if `b + delta` is a valid bound for `phi`.
+ * - `upper = true`  : `phi <= b + delta`
+ * - `upper = false` : `phi >= b + delta`
+ */
+private predicate boundedPhi(
+  SemSsaPhiNode phi, SemBound b, int delta, boolean upper, boolean fromBackEdge, int origdelta,
+  SemReason reason
+) {
+  forex(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge | edge.phiInput(phi, inp) |
+    boundedPhiCandValidForEdge(phi, b, delta, upper, fromBackEdge, origdelta, reason, inp, edge)
+  )
+}
+
+/**
+ * Holds if `e` has an upper (for `upper = true`) or lower
+ * (for `upper = false`) bound of `b`.
+ */
+private predicate baseBound(SemExpr e, int b, boolean upper) {
+  Specific::hasConstantBound(e, b, upper)
+  or
+  upper = false and
+  b = 0 and
+  semPositive(e.(SemBitAndExpr).getAnOperand()) and
+  // REVIEW: We let the language opt out here to preserve original results.
+  not Specific::ignoreZeroLowerBound(e)
+}
+
+/**
+ * Holds if the value being cast has an upper (for `upper = true`) or lower
+ * (for `upper = false`) bound within the bounds of the resulting type.
+ * For `upper = true` this means that the cast will not overflow and for
+ * `upper = false` this means that the cast will not underflow.
+ */
+private predicate safeNarrowingCast(NarrowingCastExpr cast, boolean upper) {
+  exists(int bound | bounded(cast.getOperand(), any(SemZeroBound zb), bound, upper, _, _, _) |
+    upper = true and bound <= cast.getUpperBound()
+    or
+    upper = false and bound >= cast.getLowerBound()
+  )
+}
+
+pragma[noinline]
+private predicate boundedCastExpr(
+  NarrowingCastExpr cast, SemBound b, int delta, boolean upper, boolean fromBackEdge, int origdelta,
+  SemReason reason
+) {
+  bounded(cast.getOperand(), b, delta, upper, fromBackEdge, origdelta, reason)
+}
+
+/**
+ * Holds if `b + delta` is a valid bound for `e`.
+ * - `upper = true`  : `e <= b + delta`
+ * - `upper = false` : `e >= b + delta`
+ */
+private predicate bounded(
+  SemExpr e, SemBound b, int delta, boolean upper, boolean fromBackEdge, int origdelta,
+  SemReason reason
+) {
+  not Specific::ignoreExprBound(e) and
+  (
+    e = b.getExpr(delta) and
+    (upper = true or upper = false) and
+    fromBackEdge = false and
+    origdelta = delta and
+    reason = TSemNoReason()
+    or
+    baseBound(e, delta, upper) and
+    b instanceof SemZeroBound and
+    fromBackEdge = false and
+    origdelta = delta and
+    reason = TSemNoReason()
+    or
+    exists(SemSsaVariable v, SemSsaReadPositionBlock bb |
+      boundedSsa(v, bb, b, delta, upper, fromBackEdge, origdelta, reason) and
+      e = v.getAUse() and
+      bb.getBlock() = e.getBasicBlock()
+    )
+    or
+    exists(SemExpr mid, int d1, int d2 |
+      boundFlowStep(e, mid, d1, upper) and
+      // Constants have easy, base-case bounds, so let's not infer any recursive bounds.
+      not e instanceof SemConstantIntegerExpr and
+      bounded(mid, b, d2, upper, fromBackEdge, origdelta, reason) and
+      // upper = true:  e <= mid + d1 <= b + d1 + d2 = b + delta
+      // upper = false: e >= mid + d1 >= b + d1 + d2 = b + delta
+      delta = d1 + d2
+    )
+    or
+    exists(SemSsaPhiNode phi |
+      boundedPhi(phi, b, delta, upper, fromBackEdge, origdelta, reason) and
+      e = phi.getAUse()
+    )
+    or
+    exists(SemExpr mid, int factor, int d |
+      boundFlowStepMul(e, mid, factor) and
+      not e instanceof SemConstantIntegerExpr and
+      bounded(mid, b, d, upper, fromBackEdge, origdelta, reason) and
+      b instanceof SemZeroBound and
+      delta = d * factor
+    )
+    or
+    exists(SemExpr mid, int factor, int d |
+      boundFlowStepDiv(e, mid, factor) and
+      not e instanceof SemConstantIntegerExpr and
+      bounded(mid, b, d, upper, fromBackEdge, origdelta, reason) and
+      b instanceof SemZeroBound and
+      d >= 0 and
+      delta = d / factor
+    )
+    or
+    exists(NarrowingCastExpr cast |
+      cast = e and
+      safeNarrowingCast(cast, upper.booleanNot()) and
+      boundedCastExpr(cast, b, delta, upper, fromBackEdge, origdelta, reason)
+    )
+    or
+    exists(
+      SemConditionalExpr cond, int d1, int d2, boolean fbe1, boolean fbe2, int od1, int od2,
+      SemReason r1, SemReason r2
+    |
+      cond = e and
+      boundedConditionalExpr(cond, b, upper, true, d1, fbe1, od1, r1) and
+      boundedConditionalExpr(cond, b, upper, false, d2, fbe2, od2, r2) and
+      (
+        delta = d1 and fromBackEdge = fbe1 and origdelta = od1 and reason = r1
+        or
+        delta = d2 and fromBackEdge = fbe2 and origdelta = od2 and reason = r2
+      )
+    |
+      upper = true and delta = d1.maximum(d2)
+      or
+      upper = false and delta = d1.minimum(d2)
+    )
+  )
+}
+
+private predicate boundedConditionalExpr(
+  SemConditionalExpr cond, SemBound b, boolean upper, boolean branch, int delta,
+  boolean fromBackEdge, int origdelta, SemReason reason
+) {
+  bounded(cond.getBranchExpr(branch), b, delta, upper, fromBackEdge, origdelta, reason)
+}

cpp/ql/lib/experimental/semmle/code/cpp/semantic/analysis/RangeAnalysisSpecific.qll

@@ -3,90 +3,86 @@
  */
 
 private import experimental.semmle.code.cpp.semantic.Semantic
-private import RangeAnalysisStage
-private import experimental.semmle.code.cpp.semantic.analysis.FloatDelta
 
-module CppLangImpl implements LangSig<FloatDelta> {
-  /**
-   * Holds if the specified expression should be excluded from the result of `ssaRead()`.
-   *
-   * This predicate is to keep the results identical to the original Java implementation. It should be
-   * removed once we have the new implementation matching the old results exactly.
-   */
-  predicate ignoreSsaReadCopy(SemExpr e) { none() }
+/**
+ * Holds if the specified expression should be excluded from the result of `ssaRead()`.
+ *
+ * This predicate is to keep the results identical to the original Java implementation. It should be
+ * removed once we have the new implementation matching the old results exactly.
+ */
+predicate ignoreSsaReadCopy(SemExpr e) { none() }
 
-  /**
-   * Ignore the bound on this expression.
-   *
-   * This predicate is to keep the results identical to the original Java implementation. It should be
-   * removed once we have the new implementation matching the old results exactly.
-   */
-  predicate ignoreExprBound(SemExpr e) { none() }
+/**
+ * Ignore the bound on this expression.
+ *
+ * This predicate is to keep the results identical to the original Java implementation. It should be
+ * removed once we have the new implementation matching the old results exactly.
+ */
+predicate ignoreExprBound(SemExpr e) { none() }
 
-  /**
-   * Ignore any inferred zero lower bound on this expression.
-   *
-   * This predicate is to keep the results identical to the original Java implementation. It should be
-   * removed once we have the new implementation matching the old results exactly.
-   */
-  predicate ignoreZeroLowerBound(SemExpr e) { none() }
+/**
+ * Ignore any inferred zero lower bound on this expression.
+ *
+ * This predicate is to keep the results identical to the original Java implementation. It should be
+ * removed once we have the new implementation matching the old results exactly.
+ */
+predicate ignoreZeroLowerBound(SemExpr e) { none() }
 
-  /**
-   * Holds if the specified expression should be excluded from the result of `ssaRead()`.
-   *
-   * This predicate is to keep the results identical to the original Java implementation. It should be
-   * removed once we have the new implementation matching the old results exactly.
-   */
-  predicate ignoreSsaReadArithmeticExpr(SemExpr e) { none() }
+/**
+ * Holds if the specified expression should be excluded from the result of `ssaRead()`.
+ *
+ * This predicate is to keep the results identical to the original Java implementation. It should be
+ * removed once we have the new implementation matching the old results exactly.
+ */
+predicate ignoreSsaReadArithmeticExpr(SemExpr e) { none() }
 
-  /**
-   * Holds if the specified variable should be excluded from the result of `ssaRead()`.
-   *
-   * This predicate is to keep the results identical to the original Java implementation. It should be
-   * removed once we have the new implementation matching the old results exactly.
-   */
-  predicate ignoreSsaReadAssignment(SemSsaVariable v) { none() }
+/**
+ * Holds if the specified variable should be excluded from the result of `ssaRead()`.
+ *
+ * This predicate is to keep the results identical to the original Java implementation. It should be
+ * removed once we have the new implementation matching the old results exactly.
+ */
+predicate ignoreSsaReadAssignment(SemSsaVariable v) { none() }
 
-  /**
-   * Adds additional results to `ssaRead()` that are specific to Java.
-   *
-   * This predicate handles propagation of offsets for post-increment and post-decrement expressions
-   * in exactly the same way as the old Java implementation. Once the new implementation matches the
-   * old one, we should remove this predicate and propagate deltas for all similar patterns, whether
-   * or not they come from a post-increment/decrement expression.
-   */
-  SemExpr specificSsaRead(SemSsaVariable v, float delta) { none() }
+/**
+ * Adds additional results to `ssaRead()` that are specific to Java.
+ *
+ * This predicate handles propagation of offsets for post-increment and post-decrement expressions
+ * in exactly the same way as the old Java implementation. Once the new implementation matches the
+ * old one, we should remove this predicate and propagate deltas for all similar patterns, whether
+ * or not they come from a post-increment/decrement expression.
+ */
+SemExpr specificSsaRead(SemSsaVariable v, int delta) { none() }
 
-  /**
-   * Holds if `e >= bound` (if `upper = false`) or `e <= bound` (if `upper = true`).
-   */
-  predicate hasConstantBound(SemExpr e, float bound, boolean upper) { none() }
+/**
+ * Holds if `e >= bound` (if `upper = false`) or `e <= bound` (if `upper = true`).
+ */
+predicate hasConstantBound(SemExpr e, int bound, boolean upper) { none() }
 
-  /**
-   * Holds if `e >= bound + delta` (if `upper = false`) or `e <= bound + delta` (if `upper = true`).
-   */
-  predicate hasBound(SemExpr e, SemExpr bound, float delta, boolean upper) { none() }
+/**
+ * Holds if `e >= bound + delta` (if `upper = false`) or `e <= bound + delta` (if `upper = true`).
+ */
+predicate hasBound(SemExpr e, SemExpr bound, int delta, boolean upper) { none() }
 
-  /**
-   * Holds if the value of `dest` is known to be `src + delta`.
-   */
-  predicate additionalValueFlowStep(SemExpr dest, SemExpr src, float delta) { none() }
+/**
+ * Holds if the value of `dest` is known to be `src + delta`.
+ */
+predicate additionalValueFlowStep(SemExpr dest, SemExpr src, int delta) { none() }
 
-  /**
-   * Gets the type that range analysis should use to track the result of the specified expression,
-   * if a type other than the original type of the expression is to be used.
-   *
-   * This predicate is commonly used in languages that support immutable "boxed" types that are
-   * actually references but whose values can be tracked as the type contained in the box.
-   */
-  SemType getAlternateType(SemExpr e) { none() }
+/**
+ * Gets the type that range analysis should use to track the result of the specified expression,
+ * if a type other than the original type of the expression is to be used.
+ *
+ * This predicate is commonly used in languages that support immutable "boxed" types that are
+ * actually references but whose values can be tracked as the type contained in the box.
+ */
+SemType getAlternateType(SemExpr e) { none() }
 
-  /**
-   * Gets the type that range analysis should use to track the result of the specified source
-   * variable, if a type other than the original type of the expression is to be used.
-   *
-   * This predicate is commonly used in languages that support immutable "boxed" types that are
-   * actually references but whose values can be tracked as the type contained in the box.
-   */
-  SemType getAlternateTypeForSsaVariable(SemSsaVariable var) { none() }
-}
+/**
+ * Gets the type that range analysis should use to track the result of the specified source
+ * variable, if a type other than the original type of the expression is to be used.
+ *
+ * This predicate is commonly used in languages that support immutable "boxed" types that are
+ * actually references but whose values can be tracked as the type contained in the box.
+ */
+SemType getAlternateTypeForSsaVariable(SemSsaVariable var) { none() }

cpp/ql/lib/experimental/semmle/code/cpp/semantic/analysis/RangeUtils.qll

@@ -3,138 +3,133 @@
  */
 
 private import experimental.semmle.code.cpp.semantic.Semantic
-private import RangeAnalysisSpecific
-private import RangeAnalysisStage as Range
+private import RangeAnalysisSpecific as Specific
 private import ConstantAnalysis
 
-module RangeUtil<Range::DeltaSig D, Range::LangSig<D> Lang> implements Range::UtilSig<D> {
-  /**
-   * Gets an expression that equals `v - d`.
-   */
-  SemExpr semSsaRead(SemSsaVariable v, D::Delta delta) {
-    // There are various language-specific extension points that can be removed once we no longer
-    // expect to match the original Java implementation's results exactly.
-    result = v.getAUse() and delta = D::fromInt(0)
-    or
-    exists(D::Delta d1, SemConstantIntegerExpr c |
-      result.(SemAddExpr).hasOperands(semSsaRead(v, d1), c) and
-      delta = D::fromFloat(D::toFloat(d1) - c.getIntValue()) and
-      not Lang::ignoreSsaReadArithmeticExpr(result)
-    )
-    or
-    exists(SemSubExpr sub, D::Delta d1, SemConstantIntegerExpr c |
-      result = sub and
-      sub.getLeftOperand() = semSsaRead(v, d1) and
-      sub.getRightOperand() = c and
-      delta = D::fromFloat(D::toFloat(d1) + c.getIntValue()) and
-      not Lang::ignoreSsaReadArithmeticExpr(result)
-    )
-    or
-    result = v.(SemSsaExplicitUpdate).getSourceExpr() and
-    delta = D::fromFloat(0) and
-    not Lang::ignoreSsaReadAssignment(v)
-    or
-    result = Lang::specificSsaRead(v, delta)
-    or
-    result.(SemCopyValueExpr).getOperand() = semSsaRead(v, delta) and
-    not Lang::ignoreSsaReadCopy(result)
-    or
-    result.(SemStoreExpr).getOperand() = semSsaRead(v, delta)
-  }
-
-  /**
-   * Gets a condition that tests whether `v` equals `e + delta`.
-   *
-   * If the condition evaluates to `testIsTrue`:
-   * - `isEq = true`  : `v == e + delta`
-   * - `isEq = false` : `v != e + delta`
-   */
-  SemGuard semEqFlowCond(
-    SemSsaVariable v, SemExpr e, D::Delta delta, boolean isEq, boolean testIsTrue
-  ) {
-    exists(boolean eqpolarity |
-      result.isEquality(semSsaRead(v, delta), e, eqpolarity) and
-      (testIsTrue = true or testIsTrue = false) and
-      eqpolarity.booleanXor(testIsTrue).booleanNot() = isEq
-    )
-    or
-    exists(boolean testIsTrue0 |
-      semImplies_v2(result, testIsTrue, semEqFlowCond(v, e, delta, isEq, testIsTrue0), testIsTrue0)
-    )
-  }
-
-  /**
-   * Holds if `v` is an `SsaExplicitUpdate` that equals `e + delta`.
-   */
-  predicate semSsaUpdateStep(SemSsaExplicitUpdate v, SemExpr e, D::Delta delta) {
-    exists(SemExpr defExpr | defExpr = v.getSourceExpr() |
-      defExpr.(SemCopyValueExpr).getOperand() = e and delta = D::fromFloat(0)
-      or
-      defExpr.(SemStoreExpr).getOperand() = e and delta = D::fromFloat(0)
-      or
-      defExpr.(SemAddOneExpr).getOperand() = e and delta = D::fromFloat(1)
-      or
-      defExpr.(SemSubOneExpr).getOperand() = e and delta = D::fromFloat(-1)
-      or
-      e = defExpr and
-      not (
-        defExpr instanceof SemCopyValueExpr or
-        defExpr instanceof SemStoreExpr or
-        defExpr instanceof SemAddOneExpr or
-        defExpr instanceof SemSubOneExpr
-      ) and
-      delta = D::fromFloat(0)
-    )
-  }
-
-  /**
-   * Holds if `e1 + delta` equals `e2`.
-   */
-  predicate semValueFlowStep(SemExpr e2, SemExpr e1, D::Delta delta) {
-    e2.(SemCopyValueExpr).getOperand() = e1 and delta = D::fromFloat(0)
-    or
-    e2.(SemStoreExpr).getOperand() = e1 and delta = D::fromFloat(0)
-    or
-    e2.(SemAddOneExpr).getOperand() = e1 and delta = D::fromFloat(1)
-    or
-    e2.(SemSubOneExpr).getOperand() = e1 and delta = D::fromFloat(-1)
-    or
-    Lang::additionalValueFlowStep(e2, e1, delta)
-    or
-    exists(SemExpr x | e2.(SemAddExpr).hasOperands(e1, x) |
-      D::fromInt(x.(SemConstantIntegerExpr).getIntValue()) = delta
-    )
-    or
-    exists(SemExpr x, SemSubExpr sub |
-      e2 = sub and
-      sub.getLeftOperand() = e1 and
-      sub.getRightOperand() = x
-    |
-      D::fromInt(-x.(SemConstantIntegerExpr).getIntValue()) = delta
-    )
-  }
-
-  /**
-   * Gets the type used to track the specified expression's range information.
-   *
-   * Usually, this just `e.getSemType()`, but the language can override this to track immutable boxed
-   * primitive types as the underlying primitive type.
-   */
-  SemType getTrackedType(SemExpr e) {
-    result = Lang::getAlternateType(e)
-    or
-    not exists(Lang::getAlternateType(e)) and result = e.getSemType()
-  }
-
-  /**
-   * Gets the type used to track the specified source variable's range information.
-   *
-   * Usually, this just `e.getType()`, but the language can override this to track immutable boxed
-   * primitive types as the underlying primitive type.
-   */
-  SemType getTrackedTypeForSsaVariable(SemSsaVariable var) {
-    result = Lang::getAlternateTypeForSsaVariable(var)
-    or
-    not exists(Lang::getAlternateTypeForSsaVariable(var)) and result = var.getType()
-  }
+/**
+ * Gets an expression that equals `v - d`.
+ */
+SemExpr semSsaRead(SemSsaVariable v, int delta) {
+  // There are various language-specific extension points that can be removed once we no longer
+  // expect to match the original Java implementation's results exactly.
+  result = v.getAUse() and delta = 0
+  or
+  exists(int d1, SemConstantIntegerExpr c |
+    result.(SemAddExpr).hasOperands(semSsaRead(v, d1), c) and
+    delta = d1 - c.getIntValue() and
+    not Specific::ignoreSsaReadArithmeticExpr(result)
+  )
+  or
+  exists(SemSubExpr sub, int d1, SemConstantIntegerExpr c |
+    result = sub and
+    sub.getLeftOperand() = semSsaRead(v, d1) and
+    sub.getRightOperand() = c and
+    delta = d1 + c.getIntValue() and
+    not Specific::ignoreSsaReadArithmeticExpr(result)
+  )
+  or
+  result = v.(SemSsaExplicitUpdate).getSourceExpr() and
+  delta = 0 and
+  not Specific::ignoreSsaReadAssignment(v)
+  or
+  result = Specific::specificSsaRead(v, delta)
+  or
+  result.(SemCopyValueExpr).getOperand() = semSsaRead(v, delta) and
+  not Specific::ignoreSsaReadCopy(result)
+  or
+  result.(SemStoreExpr).getOperand() = semSsaRead(v, delta)
+}
+
+/**
+ * Gets a condition that tests whether `v` equals `e + delta`.
+ *
+ * If the condition evaluates to `testIsTrue`:
+ * - `isEq = true`  : `v == e + delta`
+ * - `isEq = false` : `v != e + delta`
+ */
+SemGuard semEqFlowCond(SemSsaVariable v, SemExpr e, int delta, boolean isEq, boolean testIsTrue) {
+  exists(boolean eqpolarity |
+    result.isEquality(semSsaRead(v, delta), e, eqpolarity) and
+    (testIsTrue = true or testIsTrue = false) and
+    eqpolarity.booleanXor(testIsTrue).booleanNot() = isEq
+  )
+  or
+  exists(boolean testIsTrue0 |
+    semImplies_v2(result, testIsTrue, semEqFlowCond(v, e, delta, isEq, testIsTrue0), testIsTrue0)
+  )
+}
+
+/**
+ * Holds if `v` is an `SsaExplicitUpdate` that equals `e + delta`.
+ */
+predicate semSsaUpdateStep(SemSsaExplicitUpdate v, SemExpr e, int delta) {
+  exists(SemExpr defExpr | defExpr = v.getSourceExpr() |
+    defExpr.(SemCopyValueExpr).getOperand() = e and delta = 0
+    or
+    defExpr.(SemStoreExpr).getOperand() = e and delta = 0
+    or
+    defExpr.(SemAddOneExpr).getOperand() = e and delta = 1
+    or
+    defExpr.(SemSubOneExpr).getOperand() = e and delta = -1
+    or
+    e = defExpr and
+    not (
+      defExpr instanceof SemCopyValueExpr or
+      defExpr instanceof SemStoreExpr or
+      defExpr instanceof SemAddOneExpr or
+      defExpr instanceof SemSubOneExpr
+    ) and
+    delta = 0
+  )
+}
+
+/**
+ * Holds if `e1 + delta` equals `e2`.
+ */
+predicate semValueFlowStep(SemExpr e2, SemExpr e1, int delta) {
+  e2.(SemCopyValueExpr).getOperand() = e1 and delta = 0
+  or
+  e2.(SemStoreExpr).getOperand() = e1 and delta = 0
+  or
+  e2.(SemAddOneExpr).getOperand() = e1 and delta = 1
+  or
+  e2.(SemSubOneExpr).getOperand() = e1 and delta = -1
+  or
+  Specific::additionalValueFlowStep(e2, e1, delta)
+  or
+  exists(SemExpr x | e2.(SemAddExpr).hasOperands(e1, x) |
+    x.(SemConstantIntegerExpr).getIntValue() = delta
+  )
+  or
+  exists(SemExpr x, SemSubExpr sub |
+    e2 = sub and
+    sub.getLeftOperand() = e1 and
+    sub.getRightOperand() = x
+  |
+    x.(SemConstantIntegerExpr).getIntValue() = -delta
+  )
+}
+
+/**
+ * Gets the type used to track the specified expression's range information.
+ *
+ * Usually, this just `e.getSemType()`, but the language can override this to track immutable boxed
+ * primitive types as the underlying primitive type.
+ */
+SemType getTrackedType(SemExpr e) {
+  result = Specific::getAlternateType(e)
+  or
+  not exists(Specific::getAlternateType(e)) and result = e.getSemType()
+}
+
+/**
+ * Gets the type used to track the specified source variable's range information.
+ *
+ * Usually, this just `e.getType()`, but the language can override this to track immutable boxed
+ * primitive types as the underlying primitive type.
+ */
+SemType getTrackedTypeForSsaVariable(SemSsaVariable var) {
+  result = Specific::getAlternateTypeForSsaVariable(var)
+  or
+  not exists(Specific::getAlternateTypeForSsaVariable(var)) and result = var.getType()
 }

cpp/ql/lib/experimental/semmle/code/cpp/semantic/analysis/SignAnalysisCommon.qll

@@ -6,494 +6,496 @@
  * three-valued domain `{negative, zero, positive}`.
  */
 
-private import RangeAnalysisStage
 private import SignAnalysisSpecific as Specific
 private import experimental.semmle.code.cpp.semantic.Semantic
 private import ConstantAnalysis
 private import RangeUtils
 private import Sign
 
-module SignAnalysis<DeltaSig D, UtilSig<D> Utils> {
-  /**
-   * An SSA definition for which the analysis can compute the sign.
-   *
-   * The actual computation of the sign is done in an override of the `getSign()` predicate. The
-   * charpred of any subclass must _not_ invoke `getSign()`, directly or indirectly. This ensures
-   * that the charpred does not introduce negative recursion. The `getSign()` predicate may be
-   * recursive.
-   */
-  abstract private class SignDef instanceof SemSsaVariable {
-    final string toString() { result = super.toString() }
+/**
+ * An SSA definition for which the analysis can compute the sign.
+ *
+ * The actual computation of the sign is done in an override of the `getSign()` predicate. The
+ * charpred of any subclass must _not_ invoke `getSign()`, directly or indirectly. This ensures
+ * that the charpred does not introduce negative recursion. The `getSign()` predicate may be
+ * recursive.
+ */
+abstract private class SignDef instanceof SemSsaVariable {
+  final string toString() { result = super.toString() }
 
-    /** Gets the possible signs of this SSA definition. */
-    abstract Sign getSign();
-  }
+  /** Gets the possible signs of this SSA definition. */
+  abstract Sign getSign();
+}
 
-  /** An SSA definition whose sign is computed based on standard flow. */
-  abstract private class FlowSignDef extends SignDef {
-    abstract override Sign getSign();
-  }
+/** An SSA definition whose sign is computed based on standard flow. */
+abstract private class FlowSignDef extends SignDef {
+  abstract override Sign getSign();
+}
 
-  /** An SSA definition whose sign is determined by the sign of that definitions source expression. */
-  private class ExplicitSignDef extends FlowSignDef instanceof SemSsaExplicitUpdate {
-    final override Sign getSign() { result = semExprSign(super.getSourceExpr()) }
-  }
+/** An SSA definition whose sign is determined by the sign of that definitions source expression. */
+private class ExplicitSignDef extends FlowSignDef {
+  SemSsaExplicitUpdate update;
 
-  /** An SSA Phi definition, whose sign is the union of the signs of its inputs. */
-  private class PhiSignDef extends FlowSignDef instanceof SemSsaPhiNode {
-    final override Sign getSign() {
-      exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge |
-        edge.phiInput(this, inp) and
-        result = semSsaSign(inp, edge)
-      )
-    }
-  }
+  ExplicitSignDef() { update = this }
 
-  /** An SSA definition whose sign is computed by a language-specific implementation. */
-  abstract class CustomSignDef extends SignDef {
-    abstract override Sign getSign();
-  }
+  final override Sign getSign() { result = semExprSign(update.getSourceExpr()) }
+}
 
-  /**
-   * An expression for which the analysis can compute the sign.
-   *
-   * The actual computation of the sign is done in an override of the `getSign()` predicate. The
-   * charpred of any subclass must _not_ invoke `getSign()`, directly or indirectly. This ensures
-   * that the charpred does not introduce negative recursion. The `getSign()` predicate may be
-   * recursive.
-   *
-   * Concrete implementations extend one of the following subclasses:
-   * - `ConstantSignExpr`, for expressions with a compile-time constant value.
-   * - `FlowSignExpr`, for expressions whose sign can be computed from the signs of their operands.
-   * - `CustomsignExpr`, for expressions whose sign can be computed by a language-specific
-   *   implementation.
-   *
-   * If the same expression matches more than one of the above subclasses, the sign is computed as
-   * follows:
-   * - The sign of a `ConstantSignExpr` is computed solely from `ConstantSignExpr.getSign()`,
-   *   regardless of any other subclasses.
-   * - If a non-`ConstantSignExpr` expression matches exactly one of `FlowSignExpr` or
-   *   `CustomSignExpr`, the sign is computed by that class' `getSign()` predicate.
-   * - If a non-`ConstantSignExpr` expression matches both `FlowSignExpr` and `CustomSignExpr`, the
-   *   sign is the _intersection_ of the signs of those two classes' `getSign()` predicates. Thus,
-   *   both classes have the opportunity to _restrict_ the set of possible signs, not to generate new
-   *   possible signs.
-   * - If an expression does not match any of the three subclasses, then it can have any sign.
-   *
-   * Note that the `getSign()` predicate is introduced only in subclasses of `SignExpr`.
-   */
-  abstract class SignExpr instanceof SemExpr {
-    SignExpr() { not Specific::ignoreExprSign(this) }
+/** An SSA Phi definition, whose sign is the union of the signs of its inputs. */
+private class PhiSignDef extends FlowSignDef {
+  SemSsaPhiNode phi;
 
-    final string toString() { result = super.toString() }
+  PhiSignDef() { phi = this }
 
-    abstract Sign getSign();
-  }
-
-  /** An expression whose sign is determined by its constant numeric value. */
-  private class ConstantSignExpr extends SignExpr {
-    ConstantSignExpr() {
-      this instanceof SemConstantIntegerExpr or
-      exists(this.(SemNumericLiteralExpr).getApproximateFloatValue())
-    }
-
-    final override Sign getSign() {
-      exists(int i | this.(SemConstantIntegerExpr).getIntValue() = i |
-        i < 0 and result = TNeg()
-        or
-        i = 0 and result = TZero()
-        or
-        i > 0 and result = TPos()
-      )
-      or
-      not exists(this.(SemConstantIntegerExpr).getIntValue()) and
-      exists(float f | f = this.(SemNumericLiteralExpr).getApproximateFloatValue() |
-        f < 0 and result = TNeg()
-        or
-        f = 0 and result = TZero()
-        or
-        f > 0 and result = TPos()
-      )
-    }
-  }
-
-  abstract private class NonConstantSignExpr extends SignExpr {
-    NonConstantSignExpr() { not this instanceof ConstantSignExpr }
-
-    final override Sign getSign() {
-      // The result is the _intersection_ of the signs computed from flow and by the language.
-      (result = this.(FlowSignExpr).getSignRestriction() or not this instanceof FlowSignExpr) and
-      (result = this.(CustomSignExpr).getSignRestriction() or not this instanceof CustomSignExpr)
-    }
-  }
-
-  /** An expression whose sign is computed from the signs of its operands. */
-  abstract private class FlowSignExpr extends NonConstantSignExpr {
-    abstract Sign getSignRestriction();
-  }
-
-  /** An expression whose sign is computed by a language-specific implementation. */
-  abstract class CustomSignExpr extends NonConstantSignExpr {
-    abstract Sign getSignRestriction();
-  }
-
-  /** An expression whose sign is unknown. */
-  private class UnknownSignExpr extends SignExpr {
-    UnknownSignExpr() {
-      not this instanceof FlowSignExpr and
-      not this instanceof CustomSignExpr and
-      not this instanceof ConstantSignExpr and
-      (
-        // Only track numeric types.
-        Utils::getTrackedType(this) instanceof SemNumericType
-        or
-        // Unless the language says to track this expression anyway.
-        Specific::trackUnknownNonNumericExpr(this)
-      )
-    }
-
-    final override Sign getSign() { semAnySign(result) }
-  }
-
-  /**
-   * A `Load` expression whose sign is computed from the sign of its SSA definition, restricted by
-   * inference from any intervening guards.
-   */
-  class UseSignExpr extends FlowSignExpr {
-    SemSsaVariable v;
-
-    UseSignExpr() { v.getAUse() = this }
-
-    override Sign getSignRestriction() {
-      // Propagate via SSA
-      // Propagate the sign from the def of `v`, incorporating any inference from guards.
-      result = semSsaSign(v, any(SemSsaReadPositionBlock bb | bb.getAnExpr() = this))
-      or
-      // No block for this read. Just use the sign of the def.
-      // REVIEW: How can this happen?
-      not exists(SemSsaReadPositionBlock bb | bb.getAnExpr() = this) and
-      result = semSsaDefSign(v)
-    }
-  }
-
-  /** A binary expression whose sign is computed from the signs of its operands. */
-  private class BinarySignExpr extends FlowSignExpr {
-    SemBinaryExpr binary;
-
-    BinarySignExpr() { binary = this }
-
-    override Sign getSignRestriction() {
-      exists(SemExpr left, SemExpr right |
-        binaryExprOperands(binary, left, right) and
-        result =
-          semExprSign(pragma[only_bind_out](left))
-              .applyBinaryOp(semExprSign(pragma[only_bind_out](right)), binary.getOpcode())
-      )
-      or
-      exists(SemDivExpr div | div = binary |
-        result = semExprSign(div.getLeftOperand()) and
-        result != TZero() and
-        div.getRightOperand().(SemFloatingPointLiteralExpr).getFloatValue() = 0
-      )
-    }
-  }
-
-  pragma[nomagic]
-  private predicate binaryExprOperands(SemBinaryExpr binary, SemExpr left, SemExpr right) {
-    binary.getLeftOperand() = left and binary.getRightOperand() = right
-  }
-
-  /**
-   * A `Convert`, `Box`, or `Unbox` expression.
-   */
-  private class SemCastExpr instanceof SemUnaryExpr {
-    string toString() { result = super.toString() }
-
-    SemCastExpr() {
-      this instanceof SemConvertExpr
-      or
-      this instanceof SemBoxExpr
-      or
-      this instanceof SemUnboxExpr
-    }
-  }
-
-  /** A unary expression whose sign is computed from the sign of its operand. */
-  private class UnarySignExpr extends FlowSignExpr {
-    SemUnaryExpr unary;
-
-    UnarySignExpr() { unary = this and not this instanceof SemCastExpr }
-
-    override Sign getSignRestriction() {
-      result =
-        semExprSign(pragma[only_bind_out](unary.getOperand())).applyUnaryOp(unary.getOpcode())
-    }
-  }
-
-  /**
-   * A `Convert`, `Box`, or `Unbox` expression, whose sign is computed based on
-   * the sign of its operand and the source and destination types.
-   */
-  abstract private class CastSignExpr extends FlowSignExpr {
-    SemUnaryExpr cast;
-
-    CastSignExpr() { cast = this and cast instanceof SemCastExpr }
-
-    override Sign getSignRestriction() { result = semExprSign(cast.getOperand()) }
-  }
-
-  /**
-   * A `Convert` expression.
-   */
-  private class ConvertSignExpr extends CastSignExpr {
-    override SemConvertExpr cast;
-  }
-
-  /**
-   * A `Box` expression.
-   */
-  private class BoxSignExpr extends CastSignExpr {
-    override SemBoxExpr cast;
-  }
-
-  /**
-   * An `Unbox` expression.
-   */
-  private class UnboxSignExpr extends CastSignExpr {
-    override SemUnboxExpr cast;
-
-    UnboxSignExpr() {
-      exists(SemType fromType | fromType = Utils::getTrackedType(cast.getOperand()) |
-        // Only numeric source types are handled here.
-        fromType instanceof SemNumericType
-      )
-    }
-  }
-
-  private predicate unknownSign(SemExpr e) { e instanceof UnknownSignExpr }
-
-  /**
-   * Holds if `lowerbound` is a lower bound for `v` at `pos`. This is restricted
-   * to only include bounds for which we might determine a sign.
-   */
-  private predicate lowerBound(
-    SemExpr lowerbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isStrict
-  ) {
-    exists(boolean testIsTrue, SemRelationalExpr comp |
-      pos.hasReadOfVar(v) and
-      semGuardControlsSsaRead(semGetComparisonGuard(comp), pos, testIsTrue) and
-      not unknownSign(lowerbound)
-    |
-      testIsTrue = true and
-      comp.getLesserOperand() = lowerbound and
-      comp.getGreaterOperand() = Utils::semSsaRead(v, D::fromInt(0)) and
-      (if comp.isStrict() then isStrict = true else isStrict = false)
-      or
-      testIsTrue = false and
-      comp.getGreaterOperand() = lowerbound and
-      comp.getLesserOperand() = Utils::semSsaRead(v, D::fromInt(0)) and
-      (if comp.isStrict() then isStrict = false else isStrict = true)
+  final override Sign getSign() {
+    exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge |
+      edge.phiInput(phi, inp) and
+      result = semSsaSign(inp, edge)
     )
   }
-
-  /**
-   * Holds if `upperbound` is an upper bound for `v` at `pos`. This is restricted
-   * to only include bounds for which we might determine a sign.
-   */
-  private predicate upperBound(
-    SemExpr upperbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isStrict
-  ) {
-    exists(boolean testIsTrue, SemRelationalExpr comp |
-      pos.hasReadOfVar(v) and
-      semGuardControlsSsaRead(semGetComparisonGuard(comp), pos, testIsTrue) and
-      not unknownSign(upperbound)
-    |
-      testIsTrue = true and
-      comp.getGreaterOperand() = upperbound and
-      comp.getLesserOperand() = Utils::semSsaRead(v, D::fromInt(0)) and
-      (if comp.isStrict() then isStrict = true else isStrict = false)
-      or
-      testIsTrue = false and
-      comp.getLesserOperand() = upperbound and
-      comp.getGreaterOperand() = Utils::semSsaRead(v, D::fromInt(0)) and
-      (if comp.isStrict() then isStrict = false else isStrict = true)
-    )
-  }
-
-  /**
-   * Holds if `eqbound` is an equality/inequality for `v` at `pos`. This is
-   * restricted to only include bounds for which we might determine a sign. The
-   * boolean `isEq` gives the polarity:
-   *  - `isEq = true` : `v = eqbound`
-   *  - `isEq = false` : `v != eqbound`
-   */
-  private predicate eqBound(SemExpr eqbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isEq) {
-    exists(SemGuard guard, boolean testIsTrue, boolean polarity |
-      pos.hasReadOfVar(v) and
-      semGuardControlsSsaRead(guard, pos, testIsTrue) and
-      guard.isEquality(eqbound, Utils::semSsaRead(v, D::fromInt(0)), polarity) and
-      isEq = polarity.booleanXor(testIsTrue).booleanNot() and
-      not unknownSign(eqbound)
-    )
-  }
-
-  /**
-   * Holds if `bound` is a bound for `v` at `pos` that needs to be positive in
-   * order for `v` to be positive.
-   */
-  private predicate posBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
-    upperBound(bound, v, pos, _) or
-    eqBound(bound, v, pos, true)
-  }
-
-  /**
-   * Holds if `bound` is a bound for `v` at `pos` that needs to be negative in
-   * order for `v` to be negative.
-   */
-  private predicate negBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
-    lowerBound(bound, v, pos, _) or
-    eqBound(bound, v, pos, true)
-  }
-
-  /**
-   * Holds if `bound` is a bound for `v` at `pos` that can restrict whether `v`
-   * can be zero.
-   */
-  private predicate zeroBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
-    lowerBound(bound, v, pos, _) or
-    upperBound(bound, v, pos, _) or
-    eqBound(bound, v, pos, _)
-  }
-
-  /** Holds if `bound` allows `v` to be positive at `pos`. */
-  private predicate posBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
-    posBound(bound, v, pos) and TPos() = semExprSign(bound)
-  }
-
-  /** Holds if `bound` allows `v` to be negative at `pos`. */
-  private predicate negBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
-    negBound(bound, v, pos) and TNeg() = semExprSign(bound)
-  }
-
-  /** Holds if `bound` allows `v` to be zero at `pos`. */
-  private predicate zeroBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
-    lowerBound(bound, v, pos, _) and TNeg() = semExprSign(bound)
-    or
-    lowerBound(bound, v, pos, false) and TZero() = semExprSign(bound)
-    or
-    upperBound(bound, v, pos, _) and TPos() = semExprSign(bound)
-    or
-    upperBound(bound, v, pos, false) and TZero() = semExprSign(bound)
-    or
-    eqBound(bound, v, pos, true) and TZero() = semExprSign(bound)
-    or
-    eqBound(bound, v, pos, false) and TZero() != semExprSign(bound)
-  }
-
-  /**
-   * Holds if there is a bound that might restrict whether `v` has the sign `s`
-   * at `pos`.
-   */
-  private predicate hasGuard(SemSsaVariable v, SemSsaReadPosition pos, Sign s) {
-    s = TPos() and posBound(_, v, pos)
-    or
-    s = TNeg() and negBound(_, v, pos)
-    or
-    s = TZero() and zeroBound(_, v, pos)
-  }
-
-  /**
-   * Gets a possible sign of `v` at `pos` based on its definition, where the sign
-   * might be ruled out by a guard.
-   */
-  pragma[noinline]
-  private Sign guardedSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
-    result = semSsaDefSign(v) and
-    pos.hasReadOfVar(v) and
-    hasGuard(v, pos, result)
-  }
-
-  /**
-   * Gets a possible sign of `v` at `pos` based on its definition, where no guard
-   * can rule it out.
-   */
-  pragma[noinline]
-  private Sign unguardedSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
-    result = semSsaDefSign(v) and
-    pos.hasReadOfVar(v) and
-    not hasGuard(v, pos, result)
-  }
-
-  /**
-   * Gets a possible sign of `v` at read position `pos`, where a guard could have
-   * ruled out the sign but does not.
-   * This does not check that the definition of `v` also allows the sign.
-   */
-  private Sign guardedSsaSignOk(SemSsaVariable v, SemSsaReadPosition pos) {
-    result = TPos() and
-    forex(SemExpr bound | posBound(bound, v, pos) | posBoundOk(bound, v, pos))
-    or
-    result = TNeg() and
-    forex(SemExpr bound | negBound(bound, v, pos) | negBoundOk(bound, v, pos))
-    or
-    result = TZero() and
-    forex(SemExpr bound | zeroBound(bound, v, pos) | zeroBoundOk(bound, v, pos))
-  }
-
-  /** Gets a possible sign for `v` at `pos`. */
-  private Sign semSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
-    result = unguardedSsaSign(v, pos)
-    or
-    result = guardedSsaSign(v, pos) and
-    result = guardedSsaSignOk(v, pos)
-  }
-
-  /** Gets a possible sign for `v`. */
-  pragma[nomagic]
-  Sign semSsaDefSign(SemSsaVariable v) { result = v.(SignDef).getSign() }
-
-  /** Gets a possible sign for `e`. */
-  cached
-  Sign semExprSign(SemExpr e) {
-    exists(Sign s | s = e.(SignExpr).getSign() |
-      if
-        Utils::getTrackedType(e) instanceof SemUnsignedIntegerType and
-        s = TNeg() and
-        not Specific::ignoreTypeRestrictions(e)
-      then result = TPos()
-      else result = s
-    )
-  }
-
-  /**
-   * Dummy predicate that holds for any sign. This is added to improve readability
-   * of cases where the sign is unrestricted.
-   */
-  predicate semAnySign(Sign s) { any() }
-
-  /** Holds if `e` can be positive and cannot be negative. */
-  predicate semPositive(SemExpr e) {
-    semExprSign(e) = TPos() and
-    not semExprSign(e) = TNeg()
-  }
-
-  /** Holds if `e` can be negative and cannot be positive. */
-  predicate semNegative(SemExpr e) {
-    semExprSign(e) = TNeg() and
-    not semExprSign(e) = TPos()
-  }
-
-  /** Holds if `e` is strictly positive. */
-  predicate semStrictlyPositive(SemExpr e) {
-    semExprSign(e) = TPos() and
-    not semExprSign(e) = TNeg() and
-    not semExprSign(e) = TZero()
-  }
-
-  /** Holds if `e` is strictly negative. */
-  predicate semStrictlyNegative(SemExpr e) {
-    semExprSign(e) = TNeg() and
-    not semExprSign(e) = TPos() and
-    not semExprSign(e) = TZero()
-  }
+}
+
+/** An SSA definition whose sign is computed by a language-specific implementation. */
+abstract class CustomSignDef extends SignDef {
+  abstract override Sign getSign();
+}
+
+/**
+ * An expression for which the analysis can compute the sign.
+ *
+ * The actual computation of the sign is done in an override of the `getSign()` predicate. The
+ * charpred of any subclass must _not_ invoke `getSign()`, directly or indirectly. This ensures
+ * that the charpred does not introduce negative recursion. The `getSign()` predicate may be
+ * recursive.
+ *
+ * Concrete implementations extend one of the following subclasses:
+ * - `ConstantSignExpr`, for expressions with a compile-time constant value.
+ * - `FlowSignExpr`, for expressions whose sign can be computed from the signs of their operands.
+ * - `CustomsignExpr`, for expressions whose sign can be computed by a language-specific
+ *   implementation.
+ *
+ * If the same expression matches more than one of the above subclasses, the sign is computed as
+ * follows:
+ * - The sign of a `ConstantSignExpr` is computed solely from `ConstantSignExpr.getSign()`,
+ *   regardless of any other subclasses.
+ * - If a non-`ConstantSignExpr` expression matches exactly one of `FlowSignExpr` or
+ *   `CustomSignExpr`, the sign is computed by that class' `getSign()` predicate.
+ * - If a non-`ConstantSignExpr` expression matches both `FlowSignExpr` and `CustomSignExpr`, the
+ *   sign is the _intersection_ of the signs of those two classes' `getSign()` predicates. Thus,
+ *   both classes have the opportunity to _restrict_ the set of possible signs, not to generate new
+ *   possible signs.
+ * - If an expression does not match any of the three subclasses, then it can have any sign.
+ *
+ * Note that the `getSign()` predicate is introduced only in subclasses of `SignExpr`.
+ */
+abstract class SignExpr instanceof SemExpr {
+  SignExpr() { not Specific::ignoreExprSign(this) }
+
+  final string toString() { result = super.toString() }
+
+  abstract Sign getSign();
+}
+
+/** An expression whose sign is determined by its constant numeric value. */
+private class ConstantSignExpr extends SignExpr {
+  ConstantSignExpr() {
+    this instanceof SemConstantIntegerExpr or
+    exists(this.(SemNumericLiteralExpr).getApproximateFloatValue())
+  }
+
+  final override Sign getSign() {
+    exists(int i | this.(SemConstantIntegerExpr).getIntValue() = i |
+      i < 0 and result = TNeg()
+      or
+      i = 0 and result = TZero()
+      or
+      i > 0 and result = TPos()
+    )
+    or
+    not exists(this.(SemConstantIntegerExpr).getIntValue()) and
+    exists(float f | f = this.(SemNumericLiteralExpr).getApproximateFloatValue() |
+      f < 0 and result = TNeg()
+      or
+      f = 0 and result = TZero()
+      or
+      f > 0 and result = TPos()
+    )
+  }
+}
+
+abstract private class NonConstantSignExpr extends SignExpr {
+  NonConstantSignExpr() { not this instanceof ConstantSignExpr }
+
+  final override Sign getSign() {
+    // The result is the _intersection_ of the signs computed from flow and by the language.
+    (result = this.(FlowSignExpr).getSignRestriction() or not this instanceof FlowSignExpr) and
+    (result = this.(CustomSignExpr).getSignRestriction() or not this instanceof CustomSignExpr)
+  }
+}
+
+/** An expression whose sign is computed from the signs of its operands. */
+abstract private class FlowSignExpr extends NonConstantSignExpr {
+  abstract Sign getSignRestriction();
+}
+
+/** An expression whose sign is computed by a language-specific implementation. */
+abstract class CustomSignExpr extends NonConstantSignExpr {
+  abstract Sign getSignRestriction();
+}
+
+/** An expression whose sign is unknown. */
+private class UnknownSignExpr extends SignExpr {
+  UnknownSignExpr() {
+    not this instanceof FlowSignExpr and
+    not this instanceof CustomSignExpr and
+    not this instanceof ConstantSignExpr and
+    (
+      // Only track numeric types.
+      getTrackedType(this) instanceof SemNumericType
+      or
+      // Unless the language says to track this expression anyway.
+      Specific::trackUnknownNonNumericExpr(this)
+    )
+  }
+
+  final override Sign getSign() { semAnySign(result) }
+}
+
+/**
+ * A `Load` expression whose sign is computed from the sign of its SSA definition, restricted by
+ * inference from any intervening guards.
+ */
+class UseSignExpr extends FlowSignExpr {
+  SemSsaVariable v;
+
+  UseSignExpr() { v.getAUse() = this }
+
+  override Sign getSignRestriction() {
+    // Propagate via SSA
+    // Propagate the sign from the def of `v`, incorporating any inference from guards.
+    result = semSsaSign(v, any(SemSsaReadPositionBlock bb | bb.getAnExpr() = this))
+    or
+    // No block for this read. Just use the sign of the def.
+    // REVIEW: How can this happen?
+    not exists(SemSsaReadPositionBlock bb | bb.getAnExpr() = this) and
+    result = semSsaDefSign(v)
+  }
+}
+
+/** A binary expression whose sign is computed from the signs of its operands. */
+private class BinarySignExpr extends FlowSignExpr {
+  SemBinaryExpr binary;
+
+  BinarySignExpr() { binary = this }
+
+  override Sign getSignRestriction() {
+    exists(SemExpr left, SemExpr right |
+      binaryExprOperands(binary, left, right) and
+      result =
+        semExprSign(pragma[only_bind_out](left))
+            .applyBinaryOp(semExprSign(pragma[only_bind_out](right)), binary.getOpcode())
+    )
+    or
+    exists(SemDivExpr div | div = binary |
+      result = semExprSign(div.getLeftOperand()) and
+      result != TZero() and
+      div.getRightOperand().(SemFloatingPointLiteralExpr).getFloatValue() = 0
+    )
+  }
+}
+
+pragma[nomagic]
+private predicate binaryExprOperands(SemBinaryExpr binary, SemExpr left, SemExpr right) {
+  binary.getLeftOperand() = left and binary.getRightOperand() = right
+}
+
+/**
+ * A `Convert`, `Box`, or `Unbox` expression.
+ */
+private class SemCastExpr extends SemUnaryExpr {
+  SemCastExpr() {
+    this instanceof SemConvertExpr
+    or
+    this instanceof SemBoxExpr
+    or
+    this instanceof SemUnboxExpr
+  }
+}
+
+/** A unary expression whose sign is computed from the sign of its operand. */
+private class UnarySignExpr extends FlowSignExpr {
+  SemUnaryExpr unary;
+
+  UnarySignExpr() { unary = this and not this instanceof SemCastExpr }
+
+  override Sign getSignRestriction() {
+    result = semExprSign(pragma[only_bind_out](unary.getOperand())).applyUnaryOp(unary.getOpcode())
+  }
+}
+
+/**
+ * A `Convert`, `Box`, or `Unbox` expression, whose sign is computed based on
+ * the sign of its operand and the source and destination types.
+ */
+abstract private class CastSignExpr extends FlowSignExpr {
+  SemUnaryExpr cast;
+
+  CastSignExpr() { cast = this and cast instanceof SemCastExpr }
+
+  override Sign getSignRestriction() { result = semExprSign(cast.getOperand()) }
+}
+
+/**
+ * A `Convert` expression.
+ */
+private class ConvertSignExpr extends CastSignExpr {
+  override SemConvertExpr cast;
+}
+
+/**
+ * A `Box` expression.
+ */
+private class BoxSignExpr extends CastSignExpr {
+  override SemBoxExpr cast;
+}
+
+/**
+ * An `Unbox` expression.
+ */
+private class UnboxSignExpr extends CastSignExpr {
+  override SemUnboxExpr cast;
+
+  UnboxSignExpr() {
+    exists(SemType fromType | fromType = getTrackedType(cast.getOperand()) |
+      // Only numeric source types are handled here.
+      fromType instanceof SemNumericType
+    )
+  }
+}
+
+private predicate unknownSign(SemExpr e) { e instanceof UnknownSignExpr }
+
+/**
+ * Holds if `lowerbound` is a lower bound for `v` at `pos`. This is restricted
+ * to only include bounds for which we might determine a sign.
+ */
+private predicate lowerBound(
+  SemExpr lowerbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isStrict
+) {
+  exists(boolean testIsTrue, SemRelationalExpr comp |
+    pos.hasReadOfVar(v) and
+    semGuardControlsSsaRead(semGetComparisonGuard(comp), pos, testIsTrue) and
+    not unknownSign(lowerbound)
+  |
+    testIsTrue = true and
+    comp.getLesserOperand() = lowerbound and
+    comp.getGreaterOperand() = semSsaRead(v, 0) and
+    (if comp.isStrict() then isStrict = true else isStrict = false)
+    or
+    testIsTrue = false and
+    comp.getGreaterOperand() = lowerbound and
+    comp.getLesserOperand() = semSsaRead(v, 0) and
+    (if comp.isStrict() then isStrict = false else isStrict = true)
+  )
+}
+
+/**
+ * Holds if `upperbound` is an upper bound for `v` at `pos`. This is restricted
+ * to only include bounds for which we might determine a sign.
+ */
+private predicate upperBound(
+  SemExpr upperbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isStrict
+) {
+  exists(boolean testIsTrue, SemRelationalExpr comp |
+    pos.hasReadOfVar(v) and
+    semGuardControlsSsaRead(semGetComparisonGuard(comp), pos, testIsTrue) and
+    not unknownSign(upperbound)
+  |
+    testIsTrue = true and
+    comp.getGreaterOperand() = upperbound and
+    comp.getLesserOperand() = semSsaRead(v, 0) and
+    (if comp.isStrict() then isStrict = true else isStrict = false)
+    or
+    testIsTrue = false and
+    comp.getLesserOperand() = upperbound and
+    comp.getGreaterOperand() = semSsaRead(v, 0) and
+    (if comp.isStrict() then isStrict = false else isStrict = true)
+  )
+}
+
+/**
+ * Holds if `eqbound` is an equality/inequality for `v` at `pos`. This is
+ * restricted to only include bounds for which we might determine a sign. The
+ * boolean `isEq` gives the polarity:
+ *  - `isEq = true` : `v = eqbound`
+ *  - `isEq = false` : `v != eqbound`
+ */
+private predicate eqBound(SemExpr eqbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isEq) {
+  exists(SemGuard guard, boolean testIsTrue, boolean polarity |
+    pos.hasReadOfVar(v) and
+    semGuardControlsSsaRead(guard, pos, testIsTrue) and
+    guard.isEquality(eqbound, semSsaRead(v, 0), polarity) and
+    isEq = polarity.booleanXor(testIsTrue).booleanNot() and
+    not unknownSign(eqbound)
+  )
+}
+
+/**
+ * Holds if `bound` is a bound for `v` at `pos` that needs to be positive in
+ * order for `v` to be positive.
+ */
+private predicate posBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
+  upperBound(bound, v, pos, _) or
+  eqBound(bound, v, pos, true)
+}
+
+/**
+ * Holds if `bound` is a bound for `v` at `pos` that needs to be negative in
+ * order for `v` to be negative.
+ */
+private predicate negBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
+  lowerBound(bound, v, pos, _) or
+  eqBound(bound, v, pos, true)
+}
+
+/**
+ * Holds if `bound` is a bound for `v` at `pos` that can restrict whether `v`
+ * can be zero.
+ */
+private predicate zeroBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
+  lowerBound(bound, v, pos, _) or
+  upperBound(bound, v, pos, _) or
+  eqBound(bound, v, pos, _)
+}
+
+/** Holds if `bound` allows `v` to be positive at `pos`. */
+private predicate posBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
+  posBound(bound, v, pos) and TPos() = semExprSign(bound)
+}
+
+/** Holds if `bound` allows `v` to be negative at `pos`. */
+private predicate negBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
+  negBound(bound, v, pos) and TNeg() = semExprSign(bound)
+}
+
+/** Holds if `bound` allows `v` to be zero at `pos`. */
+private predicate zeroBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
+  lowerBound(bound, v, pos, _) and TNeg() = semExprSign(bound)
+  or
+  lowerBound(bound, v, pos, false) and TZero() = semExprSign(bound)
+  or
+  upperBound(bound, v, pos, _) and TPos() = semExprSign(bound)
+  or
+  upperBound(bound, v, pos, false) and TZero() = semExprSign(bound)
+  or
+  eqBound(bound, v, pos, true) and TZero() = semExprSign(bound)
+  or
+  eqBound(bound, v, pos, false) and TZero() != semExprSign(bound)
+}
+
+/**
+ * Holds if there is a bound that might restrict whether `v` has the sign `s`
+ * at `pos`.
+ */
+private predicate hasGuard(SemSsaVariable v, SemSsaReadPosition pos, Sign s) {
+  s = TPos() and posBound(_, v, pos)
+  or
+  s = TNeg() and negBound(_, v, pos)
+  or
+  s = TZero() and zeroBound(_, v, pos)
+}
+
+/**
+ * Gets a possible sign of `v` at `pos` based on its definition, where the sign
+ * might be ruled out by a guard.
+ */
+pragma[noinline]
+private Sign guardedSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
+  result = semSsaDefSign(v) and
+  pos.hasReadOfVar(v) and
+  hasGuard(v, pos, result)
+}
+
+/**
+ * Gets a possible sign of `v` at `pos` based on its definition, where no guard
+ * can rule it out.
+ */
+pragma[noinline]
+private Sign unguardedSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
+  result = semSsaDefSign(v) and
+  pos.hasReadOfVar(v) and
+  not hasGuard(v, pos, result)
+}
+
+/**
+ * Gets a possible sign of `v` at read position `pos`, where a guard could have
+ * ruled out the sign but does not.
+ * This does not check that the definition of `v` also allows the sign.
+ */
+private Sign guardedSsaSignOk(SemSsaVariable v, SemSsaReadPosition pos) {
+  result = TPos() and
+  forex(SemExpr bound | posBound(bound, v, pos) | posBoundOk(bound, v, pos))
+  or
+  result = TNeg() and
+  forex(SemExpr bound | negBound(bound, v, pos) | negBoundOk(bound, v, pos))
+  or
+  result = TZero() and
+  forex(SemExpr bound | zeroBound(bound, v, pos) | zeroBoundOk(bound, v, pos))
+}
+
+/** Gets a possible sign for `v` at `pos`. */
+private Sign semSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
+  result = unguardedSsaSign(v, pos)
+  or
+  result = guardedSsaSign(v, pos) and
+  result = guardedSsaSignOk(v, pos)
+}
+
+/** Gets a possible sign for `v`. */
+pragma[nomagic]
+Sign semSsaDefSign(SemSsaVariable v) { result = v.(SignDef).getSign() }
+
+/** Gets a possible sign for `e`. */
+cached
+Sign semExprSign(SemExpr e) {
+  exists(Sign s | s = e.(SignExpr).getSign() |
+    if
+      getTrackedType(e) instanceof SemUnsignedIntegerType and
+      s = TNeg() and
+      not Specific::ignoreTypeRestrictions(e)
+    then result = TPos()
+    else result = s
+  )
+}
+
+/**
+ * Dummy predicate that holds for any sign. This is added to improve readability
+ * of cases where the sign is unrestricted.
+ */
+predicate semAnySign(Sign s) { any() }
+
+/** Holds if `e` can be positive and cannot be negative. */
+predicate semPositive(SemExpr e) {
+  semExprSign(e) = TPos() and
+  not semExprSign(e) = TNeg()
+}
+
+/** Holds if `e` can be negative and cannot be positive. */
+predicate semNegative(SemExpr e) {
+  semExprSign(e) = TNeg() and
+  not semExprSign(e) = TPos()
+}
+
+/** Holds if `e` is strictly positive. */
+predicate semStrictlyPositive(SemExpr e) {
+  semExprSign(e) = TPos() and
+  not semExprSign(e) = TNeg() and
+  not semExprSign(e) = TZero()
+}
+
+/** Holds if `e` is strictly negative. */
+predicate semStrictlyNegative(SemExpr e) {
+  semExprSign(e) = TNeg() and
+  not semExprSign(e) = TPos() and
+  not semExprSign(e) = TZero()
 }

cpp/ql/lib/qlpack.yml

@@ -1,5 +1,5 @@
 name: codeql/cpp-all
-version: 0.5.3
+version: 0.4.5-dev
 groups: cpp
 dbscheme: semmlecode.cpp.dbscheme
 extractor: cpp
@@ -7,4 +7,3 @@ library: true
 upgrades: upgrades
 dependencies:
   codeql/ssa: ${workspace}
-  codeql/tutorial: ${workspace}

cpp/ql/lib/semmle/code/cpp/Function.qll

@@ -318,7 +318,7 @@ class Function extends Declaration, ControlFlowNode, AccessHolder, @function {
   MetricFunction getMetrics() { result = this }
 
   /** Holds if this function calls the function `f`. */
-  predicate calls(Function f) { this.calls(f, _) }
+  predicate calls(Function f) { exists(Locatable l | this.calls(f, l)) }
 
   /**
    * Holds if this function calls the function `f` in the `FunctionCall`
@@ -335,7 +335,7 @@ class Function extends Declaration, ControlFlowNode, AccessHolder, @function {
   }
 
   /** Holds if this function accesses a function or variable or enumerator `a`. */
-  predicate accesses(Declaration a) { this.accesses(a, _) }
+  predicate accesses(Declaration a) { exists(Locatable l | this.accesses(a, l)) }
 
   /**
    * Holds if this function accesses a function or variable or enumerator `a`

cpp/ql/lib/semmle/code/cpp/Location.qll

@@ -10,14 +10,12 @@ import semmle.code.cpp.File
  */
 class Location extends @location {
   /** Gets the container corresponding to this location. */
-  pragma[nomagic]
   Container getContainer() { this.fullLocationInfo(result, _, _, _, _) }
 
   /** Gets the file corresponding to this location, if any. */
   File getFile() { result = this.getContainer() }
 
   /** Gets the 1-based line number (inclusive) where this location starts. */
-  pragma[nomagic]
   int getStartLine() { this.fullLocationInfo(_, result, _, _, _) }
 
   /** Gets the 1-based column number (inclusive) where this location starts. */
@@ -65,6 +63,7 @@ class Location extends @location {
    * For more information, see
    * [Locations](https://codeql.github.com/docs/writing-codeql-queries/providing-locations-in-codeql-queries/).
    */
+  pragma[inline]
   predicate hasLocationInfo(
     string filepath, int startline, int startcolumn, int endline, int endcolumn
   ) {

cpp/ql/lib/semmle/code/cpp/Type.qll

@@ -816,12 +816,6 @@ private predicate floatingPointTypeMapping(
   or
   // _Float128x
   kind = 50 and base = 2 and domain = TRealDomain() and realKind = 50 and extended = true
-  or
-  // _Float16
-  kind = 52 and base = 2 and domain = TRealDomain() and realKind = 52 and extended = false
-  or
-  // _Complex _Float16
-  kind = 53 and base = 2 and domain = TComplexDomain() and realKind = 52 and extended = false
 }
 
 /**

cpp/ql/lib/semmle/code/cpp/commons/Dependency.qll

@@ -33,7 +33,7 @@ DependencyOptions getDependencyOptions() { any() }
 class DependsSource extends Element {
   DependsSource() {
     // not inside a template instantiation
-    not this.isFromTemplateInstantiation(_) or
+    not exists(Element other | this.isFromTemplateInstantiation(other)) or
     // allow DeclarationEntrys of template specializations
     this.(DeclarationEntry).getDeclaration().(Function).isConstructedFrom(_) or
     this.(DeclarationEntry).getDeclaration().(Class).isConstructedFrom(_)

cpp/ql/lib/semmle/code/cpp/commons/Exclusions.qll

@@ -69,9 +69,12 @@ predicate functionContainsDisabledCode(Function f) {
  */
 predicate functionContainsPreprocCode(Function f) {
   // `f` contains a preprocessor branch
-  exists(string file, int pbdStartLine, int fBlockStartLine, int fBlockEndLine |
+  exists(
+    PreprocessorBranchDirective pbd, string file, int pbdStartLine, int fBlockStartLine,
+    int fBlockEndLine
+  |
     functionLocation(f, file, fBlockStartLine, fBlockEndLine) and
-    pbdLocation(_, file, pbdStartLine) and
+    pbdLocation(pbd, file, pbdStartLine) and
     pbdStartLine <= fBlockEndLine and
     pbdStartLine >= fBlockStartLine
   )

cpp/ql/lib/semmle/code/cpp/commons/Printf.qll

@@ -397,8 +397,11 @@ private int lengthInBase16(float f) {
 /**
  * A class to represent format strings that occur as arguments to invocations of formatting functions.
  */
-class FormatLiteral extends Literal instanceof StringLiteral {
-  FormatLiteral() { exists(FormattingFunctionCall ffc | ffc.getFormat() = this) }
+class FormatLiteral extends Literal {
+  FormatLiteral() {
+    exists(FormattingFunctionCall ffc | ffc.getFormat() = this) and
+    this instanceof StringLiteral
+  }
 
   /**
    * Gets the function call where this format string is used.

cpp/ql/lib/semmle/code/cpp/commons/Scanf.qll

@@ -30,12 +30,15 @@ abstract class ScanfFunction extends Function {
 /**
  * The standard function `scanf` (and variations).
  */
-class Scanf extends ScanfFunction instanceof TopLevelFunction {
+class Scanf extends ScanfFunction {
   Scanf() {
-    this.hasGlobalOrStdOrBslName("scanf") or // scanf(format, args...)
-    this.hasGlobalOrStdOrBslName("wscanf") or // wscanf(format, args...)
-    this.hasGlobalName("_scanf_l") or // _scanf_l(format, locale, args...)
-    this.hasGlobalName("_wscanf_l")
+    this instanceof TopLevelFunction and
+    (
+      this.hasGlobalOrStdOrBslName("scanf") or // scanf(format, args...)
+      this.hasGlobalOrStdOrBslName("wscanf") or // wscanf(format, args...)
+      this.hasGlobalName("_scanf_l") or // _scanf_l(format, locale, args...)
+      this.hasGlobalName("_wscanf_l") // _wscanf_l(format, locale, args...)
+    )
   }
 
   override int getInputParameterIndex() { none() }
@@ -46,12 +49,15 @@ class Scanf extends ScanfFunction instanceof TopLevelFunction {
 /**
  * The standard function `fscanf` (and variations).
  */
-class Fscanf extends ScanfFunction instanceof TopLevelFunction {
+class Fscanf extends ScanfFunction {
   Fscanf() {
-    this.hasGlobalOrStdOrBslName("fscanf") or // fscanf(src_stream, format, args...)
-    this.hasGlobalOrStdOrBslName("fwscanf") or // fwscanf(src_stream, format, args...)
-    this.hasGlobalName("_fscanf_l") or // _fscanf_l(src_stream, format, locale, args...)
-    this.hasGlobalName("_fwscanf_l")
+    this instanceof TopLevelFunction and
+    (
+      this.hasGlobalOrStdOrBslName("fscanf") or // fscanf(src_stream, format, args...)
+      this.hasGlobalOrStdOrBslName("fwscanf") or // fwscanf(src_stream, format, args...)
+      this.hasGlobalName("_fscanf_l") or // _fscanf_l(src_stream, format, locale, args...)
+      this.hasGlobalName("_fwscanf_l") // _fwscanf_l(src_stream, format, locale, args...)
+    )
   }
 
   override int getInputParameterIndex() { result = 0 }
@@ -62,12 +68,15 @@ class Fscanf extends ScanfFunction instanceof TopLevelFunction {
 /**
  * The standard function `sscanf` (and variations).
  */
-class Sscanf extends ScanfFunction instanceof TopLevelFunction {
+class Sscanf extends ScanfFunction {
   Sscanf() {
-    this.hasGlobalOrStdOrBslName("sscanf") or // sscanf(src_stream, format, args...)
-    this.hasGlobalOrStdOrBslName("swscanf") or // swscanf(src, format, args...)
-    this.hasGlobalName("_sscanf_l") or // _sscanf_l(src, format, locale, args...)
-    this.hasGlobalName("_swscanf_l")
+    this instanceof TopLevelFunction and
+    (
+      this.hasGlobalOrStdOrBslName("sscanf") or // sscanf(src_stream, format, args...)
+      this.hasGlobalOrStdOrBslName("swscanf") or // swscanf(src, format, args...)
+      this.hasGlobalName("_sscanf_l") or // _sscanf_l(src, format, locale, args...)
+      this.hasGlobalName("_swscanf_l") // _swscanf_l(src, format, locale, args...)
+    )
   }
 
   override int getInputParameterIndex() { result = 0 }
@@ -78,12 +87,17 @@ class Sscanf extends ScanfFunction instanceof TopLevelFunction {
 /**
  * The standard(ish) function `snscanf` (and variations).
  */
-class Snscanf extends ScanfFunction instanceof TopLevelFunction {
+class Snscanf extends ScanfFunction {
   Snscanf() {
-    this.hasGlobalName("_snscanf") or // _snscanf(src, max_amount, format, args...)
-    this.hasGlobalName("_snwscanf") or // _snwscanf(src, max_amount, format, args...)
-    this.hasGlobalName("_snscanf_l") or // _snscanf_l(src, max_amount, format, locale, args...)
-    this.hasGlobalName("_snwscanf_l")
+    this instanceof TopLevelFunction and
+    (
+      this.hasGlobalName("_snscanf") or // _snscanf(src, max_amount, format, args...)
+      this.hasGlobalName("_snwscanf") or // _snwscanf(src, max_amount, format, args...)
+      this.hasGlobalName("_snscanf_l") or // _snscanf_l(src, max_amount, format, locale, args...)
+      this.hasGlobalName("_snwscanf_l") // _snwscanf_l(src, max_amount, format, locale, args...)
+      // note that the max_amount is not a limit on the output length, it's an input length
+      // limit used with non null-terminated strings.
+    )
   }
 
   override int getInputParameterIndex() { result = 0 }
@@ -244,7 +258,9 @@ class ScanfFormatLiteral extends Expr {
   /**
    * Gets the maximum width option of the nth input (empty string if none is given).
    */
-  string getMaxWidthOpt(int n) { this.parseConvSpec(n, _, result, _, _) }
+  string getMaxWidthOpt(int n) {
+    exists(string spec, string len, string conv | this.parseConvSpec(n, spec, result, len, conv))
+  }
 
   /**
    * Gets the maximum width of the nth input.
@@ -254,12 +270,18 @@ class ScanfFormatLiteral extends Expr {
   /**
    * Gets the length flag of the nth conversion specifier.
    */
-  string getLength(int n) { this.parseConvSpec(n, _, _, result, _) }
+  string getLength(int n) {
+    exists(string spec, string width, string conv |
+      this.parseConvSpec(n, spec, width, result, conv)
+    )
+  }
 
   /**
    * Gets the conversion character of the nth conversion specifier.
    */
-  string getConversionChar(int n) { this.parseConvSpec(n, _, _, _, result) }
+  string getConversionChar(int n) {
+    exists(string spec, string width, string len | this.parseConvSpec(n, spec, width, len, result))
+  }
 
   /**
    * Gets the maximum length of the string that can be produced by the nth

cpp/ql/lib/semmle/code/cpp/controlflow/SubBasicBlocks.qll

@@ -54,7 +54,7 @@ class SubBasicBlock extends ControlFlowNodeBase {
    * only condition under which a `SubBasicBlock` may have multiple
    * predecessors.
    */
-  predicate firstInBB() { this.getRankInBasicBlock(_) = 1 }
+  predicate firstInBB() { exists(BasicBlock bb | this.getRankInBasicBlock(bb) = 1) }
 
   /**
    * Holds if this `SubBasicBlock` comes last in its basic block. This is the

cpp/ql/lib/semmle/code/cpp/controlflow/internal/ConstantExprs.qll

@@ -441,8 +441,8 @@ library class ExprEvaluator extends int {
       req = mid.(AssignExpr).getRValue()
     )
     or
-    exists(Variable v, boolean sub1 |
-      this.interestingVariableAccess(e, _, v, sub1) and
+    exists(VariableAccess va, Variable v, boolean sub1 |
+      this.interestingVariableAccess(e, va, v, sub1) and
       req = v.getAnAssignedValue() and
       (sub1 = true implies not this.ignoreVariableAssignment(e, v, req)) and
       sub = false
@@ -876,7 +876,7 @@ private predicate nonAnalyzableVariableDefinition(Variable v, StmtParent def) {
  * empirically to have effect only on a few rare and pathological examples.
  */
 private predicate tractableVariable(Variable v) {
-  not nonAnalyzableVariableDefinition(v, _) or
+  not exists(StmtParent def | nonAnalyzableVariableDefinition(v, def)) or
   strictcount(StmtParent def | nonAnalyzableVariableDefinition(v, def)) < 1000
 }
 

cpp/ql/lib/semmle/code/cpp/dataflow/internal/DataFlowImplCommon.qll

@@ -707,8 +707,8 @@ private module Cached {
      * Gets a viable dispatch target of `call` in the context `ctx`. This is
      * restricted to those `call`s for which a context might make a difference.
      */
-    cached
-    DataFlowCallable viableImplInCallContextExt(DataFlowCall call, DataFlowCall ctx) {
+    pragma[nomagic]
+    private DataFlowCallable viableImplInCallContextExt(DataFlowCall call, DataFlowCall ctx) {
       result = viableImplInCallContext(call, ctx) and
       result = viableCallable(call)
       or
@@ -916,56 +916,28 @@ private module Cached {
     TDataFlowCallSome(DataFlowCall call)
 
   cached
-  newtype TParamNodeOption =
-    TParamNodeNone() or
-    TParamNodeSome(ParamNode p)
+  newtype TParameterPositionOption =
+    TParameterPositionNone() or
+    TParameterPositionSome(ParameterPosition pos)
 
   cached
   newtype TReturnCtx =
     TReturnCtxNone() or
     TReturnCtxNoFlowThrough() or
-    TReturnCtxMaybeFlowThrough(ReturnPosition pos)
-
-  cached
-  newtype TTypedContentApprox =
-    MkTypedContentApprox(ContentApprox c, DataFlowType t) {
-      exists(Content cont |
-        c = getContentApprox(cont) and
-        store(_, cont, _, _, t)
-      )
-    }
+    TReturnCtxMaybeFlowThrough(ReturnKindExt kind)
 
   cached
   newtype TTypedContent = MkTypedContent(Content c, DataFlowType t) { store(_, c, _, _, t) }
 
-  cached
-  TypedContent getATypedContent(TypedContentApprox c) {
-    exists(ContentApprox cls, DataFlowType t, Content cont |
-      c = MkTypedContentApprox(cls, pragma[only_bind_into](t)) and
-      result = MkTypedContent(cont, pragma[only_bind_into](t)) and
-      cls = getContentApprox(cont)
-    )
-  }
-
   cached
   newtype TAccessPathFront =
     TFrontNil(DataFlowType t) or
     TFrontHead(TypedContent tc)
 
-  cached
-  newtype TApproxAccessPathFront =
-    TApproxFrontNil(DataFlowType t) or
-    TApproxFrontHead(TypedContentApprox tc)
-
   cached
   newtype TAccessPathFrontOption =
     TAccessPathFrontNone() or
     TAccessPathFrontSome(AccessPathFront apf)
-
-  cached
-  newtype TApproxAccessPathFrontOption =
-    TApproxAccessPathFrontNone() or
-    TApproxAccessPathFrontSome(ApproxAccessPathFront apf)
 }
 
 /**
@@ -1343,15 +1315,15 @@ class DataFlowCallOption extends TDataFlowCallOption {
   }
 }
 
-/** An optional `ParamNode`. */
-class ParamNodeOption extends TParamNodeOption {
+/** An optional `ParameterPosition`. */
+class ParameterPositionOption extends TParameterPositionOption {
   string toString() {
-    this = TParamNodeNone() and
+    this = TParameterPositionNone() and
     result = "(none)"
     or
-    exists(ParamNode p |
-      this = TParamNodeSome(p) and
-      result = p.toString()
+    exists(ParameterPosition pos |
+      this = TParameterPositionSome(pos) and
+      result = pos.toString()
     )
   }
 }
@@ -1363,7 +1335,7 @@ class ParamNodeOption extends TParamNodeOption {
  *
  * - `TReturnCtxNone()`: no return flow.
  * - `TReturnCtxNoFlowThrough()`: return flow, but flow through is not possible.
- * - `TReturnCtxMaybeFlowThrough(ReturnPosition pos)`: return flow, of kind `pos`, and
+ * - `TReturnCtxMaybeFlowThrough(ReturnKindExt kind)`: return flow, of kind `kind`, and
  *    flow through may be possible.
  */
 class ReturnCtx extends TReturnCtx {
@@ -1374,87 +1346,13 @@ class ReturnCtx extends TReturnCtx {
     this = TReturnCtxNoFlowThrough() and
     result = "(no flow through)"
     or
-    exists(ReturnPosition pos |
-      this = TReturnCtxMaybeFlowThrough(pos) and
-      result = pos.toString()
+    exists(ReturnKindExt kind |
+      this = TReturnCtxMaybeFlowThrough(kind) and
+      result = kind.toString()
     )
   }
 }
 
-/** An approximated `Content` tagged with the type of a containing object. */
-class TypedContentApprox extends MkTypedContentApprox {
-  private ContentApprox c;
-  private DataFlowType t;
-
-  TypedContentApprox() { this = MkTypedContentApprox(c, t) }
-
-  /** Gets a typed content approximated by this value. */
-  TypedContent getATypedContent() { result = getATypedContent(this) }
-
-  /** Gets the content. */
-  ContentApprox getContent() { result = c }
-
-  /** Gets the container type. */
-  DataFlowType getContainerType() { result = t }
-
-  /** Gets a textual representation of this approximated content. */
-  string toString() { result = c.toString() }
-}
-
-/**
- * The front of an approximated access path. This is either a head or a nil.
- */
-abstract class ApproxAccessPathFront extends TApproxAccessPathFront {
-  abstract string toString();
-
-  abstract DataFlowType getType();
-
-  abstract boolean toBoolNonEmpty();
-
-  TypedContentApprox getHead() { this = TApproxFrontHead(result) }
-
-  pragma[nomagic]
-  TypedContent getAHead() {
-    exists(TypedContentApprox cont |
-      this = TApproxFrontHead(cont) and
-      result = cont.getATypedContent()
-    )
-  }
-}
-
-class ApproxAccessPathFrontNil extends ApproxAccessPathFront, TApproxFrontNil {
-  private DataFlowType t;
-
-  ApproxAccessPathFrontNil() { this = TApproxFrontNil(t) }
-
-  override string toString() { result = ppReprType(t) }
-
-  override DataFlowType getType() { result = t }
-
-  override boolean toBoolNonEmpty() { result = false }
-}
-
-class ApproxAccessPathFrontHead extends ApproxAccessPathFront, TApproxFrontHead {
-  private TypedContentApprox tc;
-
-  ApproxAccessPathFrontHead() { this = TApproxFrontHead(tc) }
-
-  override string toString() { result = tc.toString() }
-
-  override DataFlowType getType() { result = tc.getContainerType() }
-
-  override boolean toBoolNonEmpty() { result = true }
-}
-
-/** An optional approximated access path front. */
-class ApproxAccessPathFrontOption extends TApproxAccessPathFrontOption {
-  string toString() {
-    this = TApproxAccessPathFrontNone() and result = "<none>"
-    or
-    this = TApproxAccessPathFrontSome(any(ApproxAccessPathFront apf | result = apf.toString()))
-  }
-}
-
 /** A `Content` tagged with the type of a containing object. */
 class TypedContent extends MkTypedContent {
   private Content c;
@@ -1487,7 +1385,7 @@ abstract class AccessPathFront extends TAccessPathFront {
 
   abstract DataFlowType getType();
 
-  abstract ApproxAccessPathFront toApprox();
+  abstract boolean toBoolNonEmpty();
 
   TypedContent getHead() { this = TFrontHead(result) }
 }
@@ -1501,7 +1399,7 @@ class AccessPathFrontNil extends AccessPathFront, TFrontNil {
 
   override DataFlowType getType() { result = t }
 
-  override ApproxAccessPathFront toApprox() { result = TApproxFrontNil(t) }
+  override boolean toBoolNonEmpty() { result = false }
 }
 
 class AccessPathFrontHead extends AccessPathFront, TFrontHead {
@@ -1513,7 +1411,7 @@ class AccessPathFrontHead extends AccessPathFront, TFrontHead {
 
   override DataFlowType getType() { result = tc.getContainerType() }
 
-  override ApproxAccessPathFront toApprox() { result.getAHead() = tc }
+  override boolean toBoolNonEmpty() { result = true }
 }
 
 /** An optional access path front. */

cpp/ql/lib/semmle/code/cpp/dataflow/internal/DataFlowImplConsistency.qll

@@ -45,16 +45,6 @@ module Consistency {
     ) {
       none()
     }
-
-    /** Holds if `(c, pos, p)` should be excluded from the consistency test `uniqueParameterNodeAtPosition`. */
-    predicate uniqueParameterNodeAtPositionExclude(DataFlowCallable c, ParameterPosition pos, Node p) {
-      none()
-    }
-
-    /** Holds if `(c, pos, p)` should be excluded from the consistency test `uniqueParameterNodePosition`. */
-    predicate uniqueParameterNodePositionExclude(DataFlowCallable c, ParameterPosition pos, Node p) {
-      none()
-    }
   }
 
   private class RelevantNode extends Node {
@@ -111,7 +101,9 @@ module Consistency {
     exists(int c |
       c =
         strictcount(Node n |
-          not n.hasLocationInfo(_, _, _, _, _) and
+          not exists(string filepath, int startline, int startcolumn, int endline, int endcolumn |
+            n.hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
+          ) and
           not any(ConsistencyConfiguration conf).missingLocationExclude(n)
         ) and
       msg = "Nodes without location: " + c
@@ -256,7 +248,6 @@ module Consistency {
   query predicate uniqueParameterNodeAtPosition(
     DataFlowCallable c, ParameterPosition pos, Node p, string msg
   ) {
-    not any(ConsistencyConfiguration conf).uniqueParameterNodeAtPositionExclude(c, pos, p) and
     isParameterNode(p, c, pos) and
     not exists(unique(Node p0 | isParameterNode(p0, c, pos))) and
     msg = "Parameters with overlapping positions."
@@ -265,14 +256,8 @@ module Consistency {
   query predicate uniqueParameterNodePosition(
     DataFlowCallable c, ParameterPosition pos, Node p, string msg
   ) {
-    not any(ConsistencyConfiguration conf).uniqueParameterNodePositionExclude(c, pos, p) and
     isParameterNode(p, c, pos) and
     not exists(unique(ParameterPosition pos0 | isParameterNode(p, c, pos0))) and
     msg = "Parameter node with multiple positions."
   }
-
-  query predicate uniqueContentApprox(Content c, string msg) {
-    not exists(unique(ContentApprox approx | approx = getContentApprox(c))) and
-    msg = "Non-unique content approximation."
-  }
 }

cpp/ql/lib/semmle/code/cpp/dataflow/internal/DataFlowPrivate.qll

@@ -296,13 +296,6 @@ predicate additionalLambdaFlowStep(Node nodeFrom, Node nodeTo, boolean preserves
  */
 predicate allowParameterReturnInSelf(ParameterNode p) { none() }
 
-/** An approximated `Content`. */
-class ContentApprox = Unit;
-
-/** Gets an approximated value for content `c`. */
-pragma[inline]
-ContentApprox getContentApprox(Content c) { any() }
-
 private class MyConsistencyConfiguration extends Consistency::ConsistencyConfiguration {
   override predicate argHasPostUpdateExclude(ArgumentNode n) {
     // Is the null pointer (or something that's not really a pointer)

cpp/ql/lib/semmle/code/cpp/dataflow/internal/FlowVar.qll

@@ -450,8 +450,10 @@ module FlowVar_internal {
     }
 
     override string toString() {
-      this.definedByExpr(_, _) and
-      result = "assignment to " + v
+      exists(Expr e |
+        this.definedByExpr(e, _) and
+        result = "assignment to " + v
+      )
       or
       this.definedByInitialValue(_) and
       result = "initial value of " + v

cpp/ql/lib/semmle/code/cpp/dataflow/internal/SubBasicBlocks.qll

@@ -54,7 +54,7 @@ class SubBasicBlock extends ControlFlowNodeBase {
    * only condition under which a `SubBasicBlock` may have multiple
    * predecessors.
    */
-  predicate firstInBB() { this.getRankInBasicBlock(_) = 1 }
+  predicate firstInBB() { exists(BasicBlock bb | this.getRankInBasicBlock(bb) = 1) }
 
   /**
    * Holds if this `SubBasicBlock` comes last in its basic block. This is the

cpp/ql/lib/semmle/code/cpp/dispatch/VirtualDispatchPrototype.qll

@@ -70,8 +70,8 @@ module VirtualDispatch {
    * that is, `c` or one of its supertypes overrides `f`.
    */
   private predicate cannotInherit(Class c, MemberFunction f) {
-    exists(MemberFunction override |
-      cannotInheritHelper(c, f, _, override) and
+    exists(Class overridingType, MemberFunction override |
+      cannotInheritHelper(c, f, overridingType, override) and
       override.overrides+(f)
     )
   }

cpp/ql/lib/semmle/code/cpp/exprs/Expr.qll

@@ -53,7 +53,7 @@ class Expr extends StmtParent, @expr {
   Declaration getEnclosingDeclaration() { result = exprEnclosingElement(this) }
 
   /** Gets a child of this expression. */
-  Expr getAChild() { result = this.getChild(_) }
+  Expr getAChild() { exists(int n | result = this.getChild(n)) }
 
   /** Gets the parent of this expression, if any. */
   Element getParent() { exprparents(underlyingElement(this), _, unresolveElement(result)) }

cpp/ql/lib/semmle/code/cpp/ir/dataflow/DefaultTaintTracking.qll

@@ -1,21 +1,643 @@
 /**
- * DEPRECATED: Use `semmle.code.cpp.ir.dataflow.TaintTracking` as a replacement.
- *
  * An IR taint tracking library that uses an IR DataFlow configuration to track
  * taint from user inputs as defined by `semmle.code.cpp.security.Security`.
  */
 
 import cpp
 import semmle.code.cpp.security.Security
-private import semmle.code.cpp.ir.dataflow.internal.DefaultTaintTrackingImpl as DefaultTaintTrackingImpl
+private import semmle.code.cpp.ir.dataflow.DataFlow
+private import semmle.code.cpp.ir.dataflow.internal.DataFlowUtil
+private import semmle.code.cpp.ir.dataflow.DataFlow3
+private import semmle.code.cpp.ir.IR
+private import semmle.code.cpp.ir.dataflow.ResolveCall
+private import semmle.code.cpp.controlflow.IRGuards
+private import semmle.code.cpp.models.interfaces.Taint
+private import semmle.code.cpp.models.interfaces.DataFlow
+private import semmle.code.cpp.ir.dataflow.TaintTracking
+private import semmle.code.cpp.ir.dataflow.TaintTracking2
+private import semmle.code.cpp.ir.dataflow.TaintTracking3
+private import semmle.code.cpp.ir.dataflow.internal.ModelUtil
 
-deprecated predicate predictableOnlyFlow = DefaultTaintTrackingImpl::predictableOnlyFlow/1;
+/**
+ * A predictable instruction is one where an external user can predict
+ * the value. For example, a literal in the source code is considered
+ * predictable.
+ */
+private predicate predictableInstruction(Instruction instr) {
+  instr instanceof ConstantInstruction
+  or
+  instr instanceof StringConstantInstruction
+  or
+  // This could be a conversion on a string literal
+  predictableInstruction(instr.(UnaryInstruction).getUnary())
+}
 
-deprecated predicate tainted = DefaultTaintTrackingImpl::tainted/2;
+/**
+ * Functions that we should only allow taint to flow through (to the return
+ * value) if all but the source argument are 'predictable'.  This is done to
+ * emulate the old security library's implementation rather than due to any
+ * strong belief that this is the right approach.
+ *
+ * Note that the list itself is not very principled; it consists of all the
+ * functions listed in the old security library's [default] `isPureFunction`
+ * that have more than one argument, but are not in the old taint tracking
+ * library's `returnArgument` predicate.
+ */
+predicate predictableOnlyFlow(string name) {
+  name =
+    [
+      "strcasestr", "strchnul", "strchr", "strchrnul", "strcmp", "strcspn", "strncmp", "strndup",
+      "strnlen", "strrchr", "strspn", "strstr", "strtod", "strtof", "strtol", "strtoll", "strtoq",
+      "strtoul"
+    ]
+}
 
-deprecated predicate taintedIncludingGlobalVars =
-  DefaultTaintTrackingImpl::taintedIncludingGlobalVars/3;
+private DataFlow::Node getNodeForSource(Expr source) {
+  isUserInput(source, _) and
+  result = getNodeForExpr(source)
+}
 
-deprecated predicate globalVarFromId = DefaultTaintTrackingImpl::globalVarFromId/1;
+private DataFlow::Node getNodeForExpr(Expr node) {
+  result = DataFlow::exprNode(node)
+  or
+  // Some of the sources in `isUserInput` are intended to match the value of
+  // an expression, while others (those modeled below) are intended to match
+  // the taint that propagates out of an argument, like the `char *` argument
+  // to `gets`. It's impossible here to tell which is which, but the "access
+  // to argv" source is definitely not intended to match an output argument,
+  // and it causes false positives if we let it.
+  //
+  // This case goes together with the similar (but not identical) rule in
+  // `nodeIsBarrierIn`.
+  result = DataFlow::definitionByReferenceNodeFromArgument(node) and
+  not argv(node.(VariableAccess).getTarget())
+}
 
-deprecated module TaintedWithPath = DefaultTaintTrackingImpl::TaintedWithPath;
+private class DefaultTaintTrackingCfg extends TaintTracking::Configuration {
+  DefaultTaintTrackingCfg() { this = "DefaultTaintTrackingCfg" }
+
+  override predicate isSource(DataFlow::Node source) { source = getNodeForSource(_) }
+
+  override predicate isSink(DataFlow::Node sink) { exists(adjustedSink(sink)) }
+
+  override predicate isSanitizer(DataFlow::Node node) { nodeIsBarrier(node) }
+
+  override predicate isSanitizerIn(DataFlow::Node node) { nodeIsBarrierIn(node) }
+}
+
+private class ToGlobalVarTaintTrackingCfg extends TaintTracking::Configuration {
+  ToGlobalVarTaintTrackingCfg() { this = "GlobalVarTaintTrackingCfg" }
+
+  override predicate isSource(DataFlow::Node source) { source = getNodeForSource(_) }
+
+  override predicate isSink(DataFlow::Node sink) {
+    sink.asVariable() instanceof GlobalOrNamespaceVariable
+  }
+
+  override predicate isAdditionalTaintStep(DataFlow::Node n1, DataFlow::Node n2) {
+    writesVariable(n1.asInstruction(), n2.asVariable().(GlobalOrNamespaceVariable))
+    or
+    readsVariable(n2.asInstruction(), n1.asVariable().(GlobalOrNamespaceVariable))
+  }
+
+  override predicate isSanitizer(DataFlow::Node node) { nodeIsBarrier(node) }
+
+  override predicate isSanitizerIn(DataFlow::Node node) { nodeIsBarrierIn(node) }
+}
+
+private class FromGlobalVarTaintTrackingCfg extends TaintTracking2::Configuration {
+  FromGlobalVarTaintTrackingCfg() { this = "FromGlobalVarTaintTrackingCfg" }
+
+  override predicate isSource(DataFlow::Node source) {
+    // This set of sources should be reasonably small, which is good for
+    // performance since the set of sinks is very large.
+    exists(ToGlobalVarTaintTrackingCfg otherCfg | otherCfg.hasFlowTo(source))
+  }
+
+  override predicate isSink(DataFlow::Node sink) { exists(adjustedSink(sink)) }
+
+  override predicate isAdditionalTaintStep(DataFlow::Node n1, DataFlow::Node n2) {
+    // Additional step for flow out of variables. There is no flow _into_
+    // variables in this configuration, so this step only serves to take flow
+    // out of a variable that's a source.
+    readsVariable(n2.asInstruction(), n1.asVariable())
+  }
+
+  override predicate isSanitizer(DataFlow::Node node) { nodeIsBarrier(node) }
+
+  override predicate isSanitizerIn(DataFlow::Node node) { nodeIsBarrierIn(node) }
+}
+
+private predicate readsVariable(LoadInstruction load, Variable var) {
+  load.getSourceAddress().(VariableAddressInstruction).getAstVariable() = var
+}
+
+private predicate writesVariable(StoreInstruction store, Variable var) {
+  store.getDestinationAddress().(VariableAddressInstruction).getAstVariable() = var
+}
+
+/**
+ * A variable that has any kind of upper-bound check anywhere in the program.  This is
+ * biased towards being inclusive because there are a lot of valid ways of doing an
+ * upper bounds checks if we don't consider where it occurs, for example:
+ * ```
+ *   if (x < 10) { sink(x); }
+ *
+ *   if (10 > y) { sink(y); }
+ *
+ *   if (z > 10) { z = 10; }
+ *   sink(z);
+ * ```
+ */
+// TODO: This coarse overapproximation, ported from the old taint tracking
+// library, could be replaced with an actual semantic check that a particular
+// variable _access_ is guarded by an upper-bound check. We probably don't want
+// to do this right away since it could expose a lot of FPs that were
+// previously suppressed by this predicate by coincidence.
+private predicate hasUpperBoundsCheck(Variable var) {
+  exists(RelationalOperation oper, VariableAccess access |
+    oper.getAnOperand() = access and
+    access.getTarget() = var and
+    // Comparing to 0 is not an upper bound check
+    not oper.getAnOperand().getValue() = "0"
+  )
+}
+
+private predicate nodeIsBarrierEqualityCandidate(
+  DataFlow::Node node, Operand access, Variable checkedVar
+) {
+  readsVariable(node.asInstruction(), checkedVar) and
+  any(IRGuardCondition guard).ensuresEq(access, _, _, node.asInstruction().getBlock(), true)
+}
+
+cached
+private module Cached {
+  cached
+  predicate nodeIsBarrier(DataFlow::Node node) {
+    exists(Variable checkedVar |
+      readsVariable(node.asInstruction(), checkedVar) and
+      hasUpperBoundsCheck(checkedVar)
+    )
+    or
+    exists(Variable checkedVar, Operand access |
+      /*
+       * This node is guarded by a condition that forces the accessed variable
+       * to equal something else.  For example:
+       * ```
+       * x = taintsource()
+       * if (x == 10) {
+       *   taintsink(x); // not considered tainted
+       * }
+       * ```
+       */
+
+      nodeIsBarrierEqualityCandidate(node, access, checkedVar) and
+      readsVariable(access.getDef(), checkedVar)
+    )
+  }
+
+  cached
+  predicate nodeIsBarrierIn(DataFlow::Node node) {
+    // don't use dataflow into taint sources, as this leads to duplicate results.
+    exists(Expr source | isUserInput(source, _) |
+      node = DataFlow::exprNode(source)
+      or
+      // This case goes together with the similar (but not identical) rule in
+      // `getNodeForSource`.
+      node = DataFlow::definitionByReferenceNodeFromArgument(source)
+    )
+    or
+    // don't use dataflow into binary instructions if both operands are unpredictable
+    exists(BinaryInstruction iTo |
+      iTo = node.asInstruction() and
+      not predictableInstruction(iTo.getLeft()) and
+      not predictableInstruction(iTo.getRight()) and
+      // propagate taint from either the pointer or the offset, regardless of predictability
+      not iTo instanceof PointerArithmeticInstruction
+    )
+    or
+    // don't use dataflow through calls to pure functions if two or more operands
+    // are unpredictable
+    exists(Instruction iFrom1, Instruction iFrom2, CallInstruction iTo |
+      iTo = node.asInstruction() and
+      isPureFunction(iTo.getStaticCallTarget().getName()) and
+      iFrom1 = iTo.getAnArgument() and
+      iFrom2 = iTo.getAnArgument() and
+      not predictableInstruction(iFrom1) and
+      not predictableInstruction(iFrom2) and
+      iFrom1 != iFrom2
+    )
+  }
+
+  cached
+  Element adjustedSink(DataFlow::Node sink) {
+    // TODO: is it more appropriate to use asConvertedExpr here and avoid
+    // `getConversion*`? Or will that cause us to miss some cases where there's
+    // flow to a conversion (like a `ReferenceDereferenceExpr`) and we want to
+    // pretend there was flow to the converted `Expr` for the sake of
+    // compatibility.
+    sink.asExpr().getConversion*() = result
+    or
+    // For compatibility, send flow from arguments to parameters, even for
+    // functions with no body.
+    exists(FunctionCall call, int i |
+      sink.asExpr() = call.getArgument(pragma[only_bind_into](i)) and
+      result = resolveCall(call).getParameter(pragma[only_bind_into](i))
+    )
+    or
+    // For compatibility, send flow into a `Variable` if there is flow to any
+    // Load or Store of that variable.
+    exists(CopyInstruction copy |
+      copy.getSourceValue() = sink.asInstruction() and
+      (
+        readsVariable(copy, result) or
+        writesVariable(copy, result)
+      ) and
+      not hasUpperBoundsCheck(result)
+    )
+    or
+    // For compatibility, send flow into a `NotExpr` even if it's part of a
+    // short-circuiting condition and thus might get skipped.
+    result.(NotExpr).getOperand() = sink.asExpr()
+    or
+    // Taint postfix and prefix crement operations when their operand is tainted.
+    result.(CrementOperation).getAnOperand() = sink.asExpr()
+    or
+    // Taint `e1 += e2`, `e &= e2` and friends when `e1` or `e2` is tainted.
+    result.(AssignOperation).getAnOperand() = sink.asExpr()
+    or
+    result =
+      sink.asOperand()
+          .(SideEffectOperand)
+          .getUse()
+          .(ReadSideEffectInstruction)
+          .getArgumentDef()
+          .getUnconvertedResultExpression()
+  }
+
+  /**
+   * Step to return value of a modeled function when an input taints the
+   * dereference of the return value.
+   */
+  cached
+  predicate additionalTaintStep(DataFlow::Node n1, DataFlow::Node n2) {
+    exists(CallInstruction call, Function func, FunctionInput modelIn, FunctionOutput modelOut |
+      n1.asOperand() = callInput(call, modelIn) and
+      (
+        func.(TaintFunction).hasTaintFlow(modelIn, modelOut)
+        or
+        func.(DataFlowFunction).hasDataFlow(modelIn, modelOut)
+      ) and
+      call.getStaticCallTarget() = func and
+      modelOut.isReturnValueDeref() and
+      call = n2.asInstruction()
+    )
+  }
+}
+
+private import Cached
+
+/**
+ * Holds if `tainted` may contain taint from `source`.
+ *
+ * A tainted expression is either directly user input, or is
+ * computed from user input in a way that users can probably
+ * control the exact output of the computation.
+ *
+ * This doesn't include data flow through global variables.
+ * If you need that you must call `taintedIncludingGlobalVars`.
+ */
+cached
+predicate tainted(Expr source, Element tainted) {
+  exists(DefaultTaintTrackingCfg cfg, DataFlow::Node sink |
+    cfg.hasFlow(getNodeForSource(source), sink) and
+    tainted = adjustedSink(sink)
+  )
+}
+
+/**
+ * Holds if `tainted` may contain taint from `source`, where the taint passed
+ * through a global variable named `globalVar`.
+ *
+ * A tainted expression is either directly user input, or is
+ * computed from user input in a way that users can probably
+ * control the exact output of the computation.
+ *
+ * This version gives the same results as tainted but also includes
+ * data flow through global variables.
+ *
+ * The parameter `globalVar` is the qualified name of the last global variable
+ * used to move the value from source to tainted. If the taint did not pass
+ * through a global variable, then `globalVar = ""`.
+ */
+cached
+predicate taintedIncludingGlobalVars(Expr source, Element tainted, string globalVar) {
+  tainted(source, tainted) and
+  globalVar = ""
+  or
+  exists(
+    ToGlobalVarTaintTrackingCfg toCfg, FromGlobalVarTaintTrackingCfg fromCfg,
+    DataFlow::VariableNode variableNode, GlobalOrNamespaceVariable global, DataFlow::Node sink
+  |
+    global = variableNode.getVariable() and
+    toCfg.hasFlow(getNodeForSource(source), variableNode) and
+    fromCfg.hasFlow(variableNode, sink) and
+    tainted = adjustedSink(sink) and
+    global = globalVarFromId(globalVar)
+  )
+}
+
+/**
+ * Gets the global variable whose qualified name is `id`. Use this predicate
+ * together with `taintedIncludingGlobalVars`. Example:
+ *
+ * ```
+ * exists(string varName |
+ *   taintedIncludingGlobalVars(source, tainted, varName) and
+ *   var = globalVarFromId(varName)
+ * )
+ * ```
+ */
+GlobalOrNamespaceVariable globalVarFromId(string id) { id = result.getQualifiedName() }
+
+/**
+ * Provides definitions for augmenting source/sink pairs with data-flow paths
+ * between them. From a `@kind path-problem` query, import this module in the
+ * global scope, extend `TaintTrackingConfiguration`, and use `taintedWithPath`
+ * in place of `tainted`.
+ *
+ * Importing this module will also import the query predicates that contain the
+ * taint paths.
+ */
+module TaintedWithPath {
+  private newtype TSingleton = MkSingleton()
+
+  /**
+   * A taint-tracking configuration that matches sources and sinks in the same
+   * way as the `tainted` predicate.
+   *
+   * Override `isSink` and `taintThroughGlobals` as needed, but do not provide
+   * a characteristic predicate.
+   */
+  class TaintTrackingConfiguration extends TSingleton {
+    /** Override this to specify which elements are sources in this configuration. */
+    predicate isSource(Expr source) { exists(getNodeForSource(source)) }
+
+    /** Override this to specify which elements are sinks in this configuration. */
+    abstract predicate isSink(Element e);
+
+    /** Override this to specify which expressions are barriers in this configuration. */
+    predicate isBarrier(Expr e) { nodeIsBarrier(getNodeForExpr(e)) }
+
+    /**
+     * Override this predicate to `any()` to allow taint to flow through global
+     * variables.
+     */
+    predicate taintThroughGlobals() { none() }
+
+    /** Gets a textual representation of this element. */
+    string toString() { result = "TaintTrackingConfiguration" }
+  }
+
+  private class AdjustedConfiguration extends TaintTracking3::Configuration {
+    AdjustedConfiguration() { this = "AdjustedConfiguration" }
+
+    override predicate isSource(DataFlow::Node source) {
+      exists(TaintTrackingConfiguration cfg, Expr e |
+        cfg.isSource(e) and source = getNodeForExpr(e)
+      )
+    }
+
+    override predicate isSink(DataFlow::Node sink) {
+      exists(TaintTrackingConfiguration cfg | cfg.isSink(adjustedSink(sink)))
+    }
+
+    override predicate isAdditionalTaintStep(DataFlow::Node n1, DataFlow::Node n2) {
+      // Steps into and out of global variables
+      exists(TaintTrackingConfiguration cfg | cfg.taintThroughGlobals() |
+        writesVariable(n1.asInstruction(), n2.asVariable().(GlobalOrNamespaceVariable))
+        or
+        readsVariable(n2.asInstruction(), n1.asVariable().(GlobalOrNamespaceVariable))
+      )
+      or
+      additionalTaintStep(n1, n2)
+    }
+
+    override predicate isSanitizer(DataFlow::Node node) {
+      exists(TaintTrackingConfiguration cfg, Expr e | cfg.isBarrier(e) and node = getNodeForExpr(e))
+    }
+
+    override predicate isSanitizerIn(DataFlow::Node node) { nodeIsBarrierIn(node) }
+  }
+
+  /*
+   * A sink `Element` may map to multiple `DataFlowX::PathNode`s via (the
+   * inverse of) `adjustedSink`. For example, an `Expr` maps to all its
+   * conversions, and a `Variable` maps to all loads and stores from it. Because
+   * the path node is part of the tuple that constitutes the alert, this leads
+   * to duplicate alerts.
+   *
+   * To avoid showing duplicates, we edit the graph to replace the final node
+   * coming from the data-flow library with a node that matches exactly the
+   * `Element` sink that's requested.
+   *
+   * The same is done for sources.
+   */
+
+  private newtype TPathNode =
+    TWrapPathNode(DataFlow3::PathNode n) or
+    // There's a single newtype constructor for both sources and sinks since
+    // that makes it easiest to deal with the case where source = sink.
+    TEndpointPathNode(Element e) {
+      exists(AdjustedConfiguration cfg, DataFlow3::Node sourceNode, DataFlow3::Node sinkNode |
+        cfg.hasFlow(sourceNode, sinkNode)
+      |
+        sourceNode = getNodeForExpr(e) and
+        exists(TaintTrackingConfiguration ttCfg | ttCfg.isSource(e))
+        or
+        e = adjustedSink(sinkNode) and
+        exists(TaintTrackingConfiguration ttCfg | ttCfg.isSink(e))
+      )
+    }
+
+  /** An opaque type used for the nodes of a data-flow path. */
+  class PathNode extends TPathNode {
+    /** Gets a textual representation of this element. */
+    string toString() { none() }
+
+    /**
+     * Holds if this element is at the specified location.
+     * The location spans column `startcolumn` of line `startline` to
+     * column `endcolumn` of line `endline` in file `filepath`.
+     * For more information, see
+     * [Locations](https://codeql.github.com/docs/writing-codeql-queries/providing-locations-in-codeql-queries/).
+     */
+    pragma[inline]
+    predicate hasLocationInfo(
+      string filepath, int startline, int startcolumn, int endline, int endcolumn
+    ) {
+      none()
+    }
+  }
+
+  /**
+   * INTERNAL: Do not use.
+   */
+  module Private {
+    /** Gets a predecessor `PathNode` of `pathNode`, if any. */
+    PathNode getAPredecessor(PathNode pathNode) { edges(result, pathNode) }
+
+    /** Gets the element that `pathNode` wraps, if any. */
+    Element getElementFromPathNode(PathNode pathNode) {
+      exists(DataFlow::Node node | node = pathNode.(WrapPathNode).inner().getNode() |
+        result = node.asInstruction().getAst()
+        or
+        result = node.asOperand().getDef().getAst()
+      )
+      or
+      result = pathNode.(EndpointPathNode).inner()
+    }
+  }
+
+  private class WrapPathNode extends PathNode, TWrapPathNode {
+    DataFlow3::PathNode inner() { this = TWrapPathNode(result) }
+
+    override string toString() { result = this.inner().toString() }
+
+    override predicate hasLocationInfo(
+      string filepath, int startline, int startcolumn, int endline, int endcolumn
+    ) {
+      this.inner().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
+    }
+  }
+
+  private class EndpointPathNode extends PathNode, TEndpointPathNode {
+    Expr inner() { this = TEndpointPathNode(result) }
+
+    override string toString() { result = this.inner().toString() }
+
+    override predicate hasLocationInfo(
+      string filepath, int startline, int startcolumn, int endline, int endcolumn
+    ) {
+      this.inner()
+          .getLocation()
+          .hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
+    }
+  }
+
+  /** A PathNode whose `Element` is a source. It may also be a sink. */
+  private class InitialPathNode extends EndpointPathNode {
+    InitialPathNode() { exists(TaintTrackingConfiguration cfg | cfg.isSource(this.inner())) }
+  }
+
+  /** A PathNode whose `Element` is a sink. It may also be a source. */
+  private class FinalPathNode extends EndpointPathNode {
+    FinalPathNode() { exists(TaintTrackingConfiguration cfg | cfg.isSink(this.inner())) }
+  }
+
+  /** Holds if `(a,b)` is an edge in the graph of data flow path explanations. */
+  query predicate edges(PathNode a, PathNode b) {
+    DataFlow3::PathGraph::edges(a.(WrapPathNode).inner(), b.(WrapPathNode).inner())
+    or
+    // To avoid showing trivial-looking steps, we _replace_ the last node instead
+    // of adding an edge out of it.
+    exists(WrapPathNode sinkNode |
+      DataFlow3::PathGraph::edges(a.(WrapPathNode).inner(), sinkNode.inner()) and
+      b.(FinalPathNode).inner() = adjustedSink(sinkNode.inner().getNode())
+    )
+    or
+    // Same for the first node
+    exists(WrapPathNode sourceNode |
+      DataFlow3::PathGraph::edges(sourceNode.inner(), b.(WrapPathNode).inner()) and
+      sourceNode.inner().getNode() = getNodeForExpr(a.(InitialPathNode).inner())
+    )
+    or
+    // Finally, handle the case where the path goes directly from a source to a
+    // sink, meaning that they both need to be translated.
+    exists(WrapPathNode sinkNode, WrapPathNode sourceNode |
+      DataFlow3::PathGraph::edges(sourceNode.inner(), sinkNode.inner()) and
+      sourceNode.inner().getNode() = getNodeForExpr(a.(InitialPathNode).inner()) and
+      b.(FinalPathNode).inner() = adjustedSink(sinkNode.inner().getNode())
+    )
+  }
+
+  /**
+   * Holds if there is flow from `arg` to `out` across a call that can by summarized by the flow
+   * from `par` to `ret` within it, in the graph of data flow path explanations.
+   */
+  query predicate subpaths(PathNode arg, PathNode par, PathNode ret, PathNode out) {
+    DataFlow3::PathGraph::subpaths(arg.(WrapPathNode).inner(), par.(WrapPathNode).inner(),
+      ret.(WrapPathNode).inner(), out.(WrapPathNode).inner())
+    or
+    // To avoid showing trivial-looking steps, we _replace_ the last node instead
+    // of adding an edge out of it.
+    exists(WrapPathNode sinkNode |
+      DataFlow3::PathGraph::subpaths(arg.(WrapPathNode).inner(), par.(WrapPathNode).inner(),
+        ret.(WrapPathNode).inner(), sinkNode.inner()) and
+      out.(FinalPathNode).inner() = adjustedSink(sinkNode.inner().getNode())
+    )
+    or
+    // Same for the first node
+    exists(WrapPathNode sourceNode |
+      DataFlow3::PathGraph::subpaths(sourceNode.inner(), par.(WrapPathNode).inner(),
+        ret.(WrapPathNode).inner(), out.(WrapPathNode).inner()) and
+      sourceNode.inner().getNode() = getNodeForExpr(arg.(InitialPathNode).inner())
+    )
+    or
+    // Finally, handle the case where the path goes directly from a source to a
+    // sink, meaning that they both need to be translated.
+    exists(WrapPathNode sinkNode, WrapPathNode sourceNode |
+      DataFlow3::PathGraph::subpaths(sourceNode.inner(), par.(WrapPathNode).inner(),
+        ret.(WrapPathNode).inner(), sinkNode.inner()) and
+      sourceNode.inner().getNode() = getNodeForExpr(arg.(InitialPathNode).inner()) and
+      out.(FinalPathNode).inner() = adjustedSink(sinkNode.inner().getNode())
+    )
+  }
+
+  /** Holds if `n` is a node in the graph of data flow path explanations. */
+  query predicate nodes(PathNode n, string key, string val) {
+    key = "semmle.label" and val = n.toString()
+  }
+
+  /**
+   * Holds if `tainted` may contain taint from `source`, where `sourceNode` and
+   * `sinkNode` are the corresponding `PathNode`s that can be used in a query
+   * to provide path explanations. Extend `TaintTrackingConfiguration` to use
+   * this predicate.
+   *
+   * A tainted expression is either directly user input, or is computed from
+   * user input in a way that users can probably control the exact output of
+   * the computation.
+   */
+  predicate taintedWithPath(Expr source, Element tainted, PathNode sourceNode, PathNode sinkNode) {
+    exists(AdjustedConfiguration cfg, DataFlow3::Node flowSource, DataFlow3::Node flowSink |
+      source = sourceNode.(InitialPathNode).inner() and
+      flowSource = getNodeForExpr(source) and
+      cfg.hasFlow(flowSource, flowSink) and
+      tainted = adjustedSink(flowSink) and
+      tainted = sinkNode.(FinalPathNode).inner()
+    )
+  }
+
+  private predicate isGlobalVariablePathNode(WrapPathNode n) {
+    n.inner().getNode().asVariable() instanceof GlobalOrNamespaceVariable
+  }
+
+  private predicate edgesWithoutGlobals(PathNode a, PathNode b) {
+    edges(a, b) and
+    not isGlobalVariablePathNode(a) and
+    not isGlobalVariablePathNode(b)
+  }
+
+  /**
+   * Holds if `tainted` can be reached from a taint source without passing
+   * through a global variable.
+   */
+  predicate taintedWithoutGlobals(Element tainted) {
+    exists(AdjustedConfiguration cfg, PathNode sourceNode, FinalPathNode sinkNode |
+      cfg.isSource(sourceNode.(WrapPathNode).inner().getNode()) and
+      edgesWithoutGlobals+(sourceNode, sinkNode) and
+      tainted = sinkNode.inner()
+    )
+  }
+}

cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowImplCommon.qll

@@ -707,8 +707,8 @@ private module Cached {
      * Gets a viable dispatch target of `call` in the context `ctx`. This is
      * restricted to those `call`s for which a context might make a difference.
      */
-    cached
-    DataFlowCallable viableImplInCallContextExt(DataFlowCall call, DataFlowCall ctx) {
+    pragma[nomagic]
+    private DataFlowCallable viableImplInCallContextExt(DataFlowCall call, DataFlowCall ctx) {
       result = viableImplInCallContext(call, ctx) and
       result = viableCallable(call)
       or
@@ -916,56 +916,28 @@ private module Cached {
     TDataFlowCallSome(DataFlowCall call)
 
   cached
-  newtype TParamNodeOption =
-    TParamNodeNone() or
-    TParamNodeSome(ParamNode p)
+  newtype TParameterPositionOption =
+    TParameterPositionNone() or
+    TParameterPositionSome(ParameterPosition pos)
 
   cached
   newtype TReturnCtx =
     TReturnCtxNone() or
     TReturnCtxNoFlowThrough() or
-    TReturnCtxMaybeFlowThrough(ReturnPosition pos)
-
-  cached
-  newtype TTypedContentApprox =
-    MkTypedContentApprox(ContentApprox c, DataFlowType t) {
-      exists(Content cont |
-        c = getContentApprox(cont) and
-        store(_, cont, _, _, t)
-      )
-    }
+    TReturnCtxMaybeFlowThrough(ReturnKindExt kind)
 
   cached
   newtype TTypedContent = MkTypedContent(Content c, DataFlowType t) { store(_, c, _, _, t) }
 
-  cached
-  TypedContent getATypedContent(TypedContentApprox c) {
-    exists(ContentApprox cls, DataFlowType t, Content cont |
-      c = MkTypedContentApprox(cls, pragma[only_bind_into](t)) and
-      result = MkTypedContent(cont, pragma[only_bind_into](t)) and
-      cls = getContentApprox(cont)
-    )
-  }
-
   cached
   newtype TAccessPathFront =
     TFrontNil(DataFlowType t) or
     TFrontHead(TypedContent tc)
 
-  cached
-  newtype TApproxAccessPathFront =
-    TApproxFrontNil(DataFlowType t) or
-    TApproxFrontHead(TypedContentApprox tc)
-
   cached
   newtype TAccessPathFrontOption =
     TAccessPathFrontNone() or
     TAccessPathFrontSome(AccessPathFront apf)
-
-  cached
-  newtype TApproxAccessPathFrontOption =
-    TApproxAccessPathFrontNone() or
-    TApproxAccessPathFrontSome(ApproxAccessPathFront apf)
 }
 
 /**
@@ -1343,15 +1315,15 @@ class DataFlowCallOption extends TDataFlowCallOption {
   }
 }
 
-/** An optional `ParamNode`. */
-class ParamNodeOption extends TParamNodeOption {
+/** An optional `ParameterPosition`. */
+class ParameterPositionOption extends TParameterPositionOption {
   string toString() {
-    this = TParamNodeNone() and
+    this = TParameterPositionNone() and
     result = "(none)"
     or
-    exists(ParamNode p |
-      this = TParamNodeSome(p) and
-      result = p.toString()
+    exists(ParameterPosition pos |
+      this = TParameterPositionSome(pos) and
+      result = pos.toString()
     )
   }
 }
@@ -1363,7 +1335,7 @@ class ParamNodeOption extends TParamNodeOption {
  *
  * - `TReturnCtxNone()`: no return flow.
  * - `TReturnCtxNoFlowThrough()`: return flow, but flow through is not possible.
- * - `TReturnCtxMaybeFlowThrough(ReturnPosition pos)`: return flow, of kind `pos`, and
+ * - `TReturnCtxMaybeFlowThrough(ReturnKindExt kind)`: return flow, of kind `kind`, and
  *    flow through may be possible.
  */
 class ReturnCtx extends TReturnCtx {
@@ -1374,87 +1346,13 @@ class ReturnCtx extends TReturnCtx {
     this = TReturnCtxNoFlowThrough() and
     result = "(no flow through)"
     or
-    exists(ReturnPosition pos |
-      this = TReturnCtxMaybeFlowThrough(pos) and
-      result = pos.toString()
+    exists(ReturnKindExt kind |
+      this = TReturnCtxMaybeFlowThrough(kind) and
+      result = kind.toString()
     )
   }
 }
 
-/** An approximated `Content` tagged with the type of a containing object. */
-class TypedContentApprox extends MkTypedContentApprox {
-  private ContentApprox c;
-  private DataFlowType t;
-
-  TypedContentApprox() { this = MkTypedContentApprox(c, t) }
-
-  /** Gets a typed content approximated by this value. */
-  TypedContent getATypedContent() { result = getATypedContent(this) }
-
-  /** Gets the content. */
-  ContentApprox getContent() { result = c }
-
-  /** Gets the container type. */
-  DataFlowType getContainerType() { result = t }
-
-  /** Gets a textual representation of this approximated content. */
-  string toString() { result = c.toString() }
-}
-
-/**
- * The front of an approximated access path. This is either a head or a nil.
- */
-abstract class ApproxAccessPathFront extends TApproxAccessPathFront {
-  abstract string toString();
-
-  abstract DataFlowType getType();
-
-  abstract boolean toBoolNonEmpty();
-
-  TypedContentApprox getHead() { this = TApproxFrontHead(result) }
-
-  pragma[nomagic]
-  TypedContent getAHead() {
-    exists(TypedContentApprox cont |
-      this = TApproxFrontHead(cont) and
-      result = cont.getATypedContent()
-    )
-  }
-}
-
-class ApproxAccessPathFrontNil extends ApproxAccessPathFront, TApproxFrontNil {
-  private DataFlowType t;
-
-  ApproxAccessPathFrontNil() { this = TApproxFrontNil(t) }
-
-  override string toString() { result = ppReprType(t) }
-
-  override DataFlowType getType() { result = t }
-
-  override boolean toBoolNonEmpty() { result = false }
-}
-
-class ApproxAccessPathFrontHead extends ApproxAccessPathFront, TApproxFrontHead {
-  private TypedContentApprox tc;
-
-  ApproxAccessPathFrontHead() { this = TApproxFrontHead(tc) }
-
-  override string toString() { result = tc.toString() }
-
-  override DataFlowType getType() { result = tc.getContainerType() }
-
-  override boolean toBoolNonEmpty() { result = true }
-}
-
-/** An optional approximated access path front. */
-class ApproxAccessPathFrontOption extends TApproxAccessPathFrontOption {
-  string toString() {
-    this = TApproxAccessPathFrontNone() and result = "<none>"
-    or
-    this = TApproxAccessPathFrontSome(any(ApproxAccessPathFront apf | result = apf.toString()))
-  }
-}
-
 /** A `Content` tagged with the type of a containing object. */
 class TypedContent extends MkTypedContent {
   private Content c;
@@ -1487,7 +1385,7 @@ abstract class AccessPathFront extends TAccessPathFront {
 
   abstract DataFlowType getType();
 
-  abstract ApproxAccessPathFront toApprox();
+  abstract boolean toBoolNonEmpty();
 
   TypedContent getHead() { this = TFrontHead(result) }
 }
@@ -1501,7 +1399,7 @@ class AccessPathFrontNil extends AccessPathFront, TFrontNil {
 
   override DataFlowType getType() { result = t }
 
-  override ApproxAccessPathFront toApprox() { result = TApproxFrontNil(t) }
+  override boolean toBoolNonEmpty() { result = false }
 }
 
 class AccessPathFrontHead extends AccessPathFront, TFrontHead {
@@ -1513,7 +1411,7 @@ class AccessPathFrontHead extends AccessPathFront, TFrontHead {
 
   override DataFlowType getType() { result = tc.getContainerType() }
 
-  override ApproxAccessPathFront toApprox() { result.getAHead() = tc }
+  override boolean toBoolNonEmpty() { result = true }
 }
 
 /** An optional access path front. */

cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowImplConsistency.qll

@@ -45,16 +45,6 @@ module Consistency {
     ) {
       none()
     }
-
-    /** Holds if `(c, pos, p)` should be excluded from the consistency test `uniqueParameterNodeAtPosition`. */
-    predicate uniqueParameterNodeAtPositionExclude(DataFlowCallable c, ParameterPosition pos, Node p) {
-      none()
-    }
-
-    /** Holds if `(c, pos, p)` should be excluded from the consistency test `uniqueParameterNodePosition`. */
-    predicate uniqueParameterNodePositionExclude(DataFlowCallable c, ParameterPosition pos, Node p) {
-      none()
-    }
   }
 
   private class RelevantNode extends Node {
@@ -111,7 +101,9 @@ module Consistency {
     exists(int c |
       c =
         strictcount(Node n |
-          not n.hasLocationInfo(_, _, _, _, _) and
+          not exists(string filepath, int startline, int startcolumn, int endline, int endcolumn |
+            n.hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
+          ) and
           not any(ConsistencyConfiguration conf).missingLocationExclude(n)
         ) and
       msg = "Nodes without location: " + c
@@ -256,7 +248,6 @@ module Consistency {
   query predicate uniqueParameterNodeAtPosition(
     DataFlowCallable c, ParameterPosition pos, Node p, string msg
   ) {
-    not any(ConsistencyConfiguration conf).uniqueParameterNodeAtPositionExclude(c, pos, p) and
     isParameterNode(p, c, pos) and
     not exists(unique(Node p0 | isParameterNode(p0, c, pos))) and
     msg = "Parameters with overlapping positions."
@@ -265,14 +256,8 @@ module Consistency {
   query predicate uniqueParameterNodePosition(
     DataFlowCallable c, ParameterPosition pos, Node p, string msg
   ) {
-    not any(ConsistencyConfiguration conf).uniqueParameterNodePositionExclude(c, pos, p) and
     isParameterNode(p, c, pos) and
     not exists(unique(ParameterPosition pos0 | isParameterNode(p, c, pos0))) and
     msg = "Parameter node with multiple positions."
   }
-
-  query predicate uniqueContentApprox(Content c, string msg) {
-    not exists(unique(ContentApprox approx | approx = getContentApprox(c))) and
-    msg = "Non-unique content approximation."
-  }
 }

cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowPrivate.qll

@@ -400,13 +400,6 @@ predicate additionalLambdaFlowStep(Node nodeFrom, Node nodeTo, boolean preserves
  */
 predicate allowParameterReturnInSelf(ParameterNode p) { none() }
 
-/** An approximated `Content`. */
-class ContentApprox = Unit;
-
-/** Gets an approximated value for content `c`. */
-pragma[inline]
-ContentApprox getContentApprox(Content c) { any() }
-
 private class MyConsistencyConfiguration extends Consistency::ConsistencyConfiguration {
   override predicate argHasPostUpdateExclude(ArgumentNode n) {
     // The rules for whether an IR argument gets a post-update node are too

cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DefaultTaintTrackingImpl.qll

@@ -1,644 +0,0 @@
-/**
- * INTERNAL: Do not use.
- *
- * An IR taint tracking library that uses an IR DataFlow configuration to track
- * taint from user inputs as defined by `semmle.code.cpp.security.Security`.
- */
-
-import cpp
-import semmle.code.cpp.security.Security
-private import semmle.code.cpp.ir.dataflow.DataFlow
-private import semmle.code.cpp.ir.dataflow.internal.DataFlowUtil
-private import semmle.code.cpp.ir.dataflow.DataFlow3
-private import semmle.code.cpp.ir.IR
-private import semmle.code.cpp.ir.dataflow.ResolveCall
-private import semmle.code.cpp.controlflow.IRGuards
-private import semmle.code.cpp.models.interfaces.Taint
-private import semmle.code.cpp.models.interfaces.DataFlow
-private import semmle.code.cpp.ir.dataflow.TaintTracking
-private import semmle.code.cpp.ir.dataflow.TaintTracking2
-private import semmle.code.cpp.ir.dataflow.TaintTracking3
-private import semmle.code.cpp.ir.dataflow.internal.ModelUtil
-
-/**
- * A predictable instruction is one where an external user can predict
- * the value. For example, a literal in the source code is considered
- * predictable.
- */
-private predicate predictableInstruction(Instruction instr) {
-  instr instanceof ConstantInstruction
-  or
-  instr instanceof StringConstantInstruction
-  or
-  // This could be a conversion on a string literal
-  predictableInstruction(instr.(UnaryInstruction).getUnary())
-}
-
-/**
- * Functions that we should only allow taint to flow through (to the return
- * value) if all but the source argument are 'predictable'.  This is done to
- * emulate the old security library's implementation rather than due to any
- * strong belief that this is the right approach.
- *
- * Note that the list itself is not very principled; it consists of all the
- * functions listed in the old security library's [default] `isPureFunction`
- * that have more than one argument, but are not in the old taint tracking
- * library's `returnArgument` predicate.
- */
-predicate predictableOnlyFlow(string name) {
-  name =
-    [
-      "strcasestr", "strchnul", "strchr", "strchrnul", "strcmp", "strcspn", "strncmp", "strndup",
-      "strnlen", "strrchr", "strspn", "strstr", "strtod", "strtof", "strtol", "strtoll", "strtoq",
-      "strtoul"
-    ]
-}
-
-private DataFlow::Node getNodeForSource(Expr source) {
-  isUserInput(source, _) and
-  result = getNodeForExpr(source)
-}
-
-private DataFlow::Node getNodeForExpr(Expr node) {
-  result = DataFlow::exprNode(node)
-  or
-  // Some of the sources in `isUserInput` are intended to match the value of
-  // an expression, while others (those modeled below) are intended to match
-  // the taint that propagates out of an argument, like the `char *` argument
-  // to `gets`. It's impossible here to tell which is which, but the "access
-  // to argv" source is definitely not intended to match an output argument,
-  // and it causes false positives if we let it.
-  //
-  // This case goes together with the similar (but not identical) rule in
-  // `nodeIsBarrierIn`.
-  result = DataFlow::definitionByReferenceNodeFromArgument(node) and
-  not argv(node.(VariableAccess).getTarget())
-}
-
-private class DefaultTaintTrackingCfg extends TaintTracking::Configuration {
-  DefaultTaintTrackingCfg() { this = "DefaultTaintTrackingCfg" }
-
-  override predicate isSource(DataFlow::Node source) { source = getNodeForSource(_) }
-
-  override predicate isSink(DataFlow::Node sink) { exists(adjustedSink(sink)) }
-
-  override predicate isSanitizer(DataFlow::Node node) { nodeIsBarrier(node) }
-
-  override predicate isSanitizerIn(DataFlow::Node node) { nodeIsBarrierIn(node) }
-}
-
-private class ToGlobalVarTaintTrackingCfg extends TaintTracking::Configuration {
-  ToGlobalVarTaintTrackingCfg() { this = "GlobalVarTaintTrackingCfg" }
-
-  override predicate isSource(DataFlow::Node source) { source = getNodeForSource(_) }
-
-  override predicate isSink(DataFlow::Node sink) {
-    sink.asVariable() instanceof GlobalOrNamespaceVariable
-  }
-
-  override predicate isAdditionalTaintStep(DataFlow::Node n1, DataFlow::Node n2) {
-    writesVariable(n1.asInstruction(), n2.asVariable().(GlobalOrNamespaceVariable))
-    or
-    readsVariable(n2.asInstruction(), n1.asVariable().(GlobalOrNamespaceVariable))
-  }
-
-  override predicate isSanitizer(DataFlow::Node node) { nodeIsBarrier(node) }
-
-  override predicate isSanitizerIn(DataFlow::Node node) { nodeIsBarrierIn(node) }
-}
-
-private class FromGlobalVarTaintTrackingCfg extends TaintTracking2::Configuration {
-  FromGlobalVarTaintTrackingCfg() { this = "FromGlobalVarTaintTrackingCfg" }
-
-  override predicate isSource(DataFlow::Node source) {
-    // This set of sources should be reasonably small, which is good for
-    // performance since the set of sinks is very large.
-    exists(ToGlobalVarTaintTrackingCfg otherCfg | otherCfg.hasFlowTo(source))
-  }
-
-  override predicate isSink(DataFlow::Node sink) { exists(adjustedSink(sink)) }
-
-  override predicate isAdditionalTaintStep(DataFlow::Node n1, DataFlow::Node n2) {
-    // Additional step for flow out of variables. There is no flow _into_
-    // variables in this configuration, so this step only serves to take flow
-    // out of a variable that's a source.
-    readsVariable(n2.asInstruction(), n1.asVariable())
-  }
-
-  override predicate isSanitizer(DataFlow::Node node) { nodeIsBarrier(node) }
-
-  override predicate isSanitizerIn(DataFlow::Node node) { nodeIsBarrierIn(node) }
-}
-
-private predicate readsVariable(LoadInstruction load, Variable var) {
-  load.getSourceAddress().(VariableAddressInstruction).getAstVariable() = var
-}
-
-private predicate writesVariable(StoreInstruction store, Variable var) {
-  store.getDestinationAddress().(VariableAddressInstruction).getAstVariable() = var
-}
-
-/**
- * A variable that has any kind of upper-bound check anywhere in the program.  This is
- * biased towards being inclusive because there are a lot of valid ways of doing an
- * upper bounds checks if we don't consider where it occurs, for example:
- * ```
- *   if (x < 10) { sink(x); }
- *
- *   if (10 > y) { sink(y); }
- *
- *   if (z > 10) { z = 10; }
- *   sink(z);
- * ```
- */
-// TODO: This coarse overapproximation, ported from the old taint tracking
-// library, could be replaced with an actual semantic check that a particular
-// variable _access_ is guarded by an upper-bound check. We probably don't want
-// to do this right away since it could expose a lot of FPs that were
-// previously suppressed by this predicate by coincidence.
-private predicate hasUpperBoundsCheck(Variable var) {
-  exists(RelationalOperation oper, VariableAccess access |
-    oper.getAnOperand() = access and
-    access.getTarget() = var and
-    // Comparing to 0 is not an upper bound check
-    not oper.getAnOperand().getValue() = "0"
-  )
-}
-
-private predicate nodeIsBarrierEqualityCandidate(
-  DataFlow::Node node, Operand access, Variable checkedVar
-) {
-  readsVariable(node.asInstruction(), checkedVar) and
-  any(IRGuardCondition guard).ensuresEq(access, _, _, node.asInstruction().getBlock(), true)
-}
-
-cached
-private module Cached {
-  cached
-  predicate nodeIsBarrier(DataFlow::Node node) {
-    exists(Variable checkedVar |
-      readsVariable(node.asInstruction(), checkedVar) and
-      hasUpperBoundsCheck(checkedVar)
-    )
-    or
-    exists(Variable checkedVar, Operand access |
-      /*
-       * This node is guarded by a condition that forces the accessed variable
-       * to equal something else.  For example:
-       * ```
-       * x = taintsource()
-       * if (x == 10) {
-       *   taintsink(x); // not considered tainted
-       * }
-       * ```
-       */
-
-      nodeIsBarrierEqualityCandidate(node, access, checkedVar) and
-      readsVariable(access.getDef(), checkedVar)
-    )
-  }
-
-  cached
-  predicate nodeIsBarrierIn(DataFlow::Node node) {
-    // don't use dataflow into taint sources, as this leads to duplicate results.
-    exists(Expr source | isUserInput(source, _) |
-      node = DataFlow::exprNode(source)
-      or
-      // This case goes together with the similar (but not identical) rule in
-      // `getNodeForSource`.
-      node = DataFlow::definitionByReferenceNodeFromArgument(source)
-    )
-    or
-    // don't use dataflow into binary instructions if both operands are unpredictable
-    exists(BinaryInstruction iTo |
-      iTo = node.asInstruction() and
-      not predictableInstruction(iTo.getLeft()) and
-      not predictableInstruction(iTo.getRight()) and
-      // propagate taint from either the pointer or the offset, regardless of predictability
-      not iTo instanceof PointerArithmeticInstruction
-    )
-    or
-    // don't use dataflow through calls to pure functions if two or more operands
-    // are unpredictable
-    exists(Instruction iFrom1, Instruction iFrom2, CallInstruction iTo |
-      iTo = node.asInstruction() and
-      isPureFunction(iTo.getStaticCallTarget().getName()) and
-      iFrom1 = iTo.getAnArgument() and
-      iFrom2 = iTo.getAnArgument() and
-      not predictableInstruction(iFrom1) and
-      not predictableInstruction(iFrom2) and
-      iFrom1 != iFrom2
-    )
-  }
-
-  cached
-  Element adjustedSink(DataFlow::Node sink) {
-    // TODO: is it more appropriate to use asConvertedExpr here and avoid
-    // `getConversion*`? Or will that cause us to miss some cases where there's
-    // flow to a conversion (like a `ReferenceDereferenceExpr`) and we want to
-    // pretend there was flow to the converted `Expr` for the sake of
-    // compatibility.
-    sink.asExpr().getConversion*() = result
-    or
-    // For compatibility, send flow from arguments to parameters, even for
-    // functions with no body.
-    exists(FunctionCall call, int i |
-      sink.asExpr() = call.getArgument(pragma[only_bind_into](i)) and
-      result = resolveCall(call).getParameter(pragma[only_bind_into](i))
-    )
-    or
-    // For compatibility, send flow into a `Variable` if there is flow to any
-    // Load or Store of that variable.
-    exists(CopyInstruction copy |
-      copy.getSourceValue() = sink.asInstruction() and
-      (
-        readsVariable(copy, result) or
-        writesVariable(copy, result)
-      ) and
-      not hasUpperBoundsCheck(result)
-    )
-    or
-    // For compatibility, send flow into a `NotExpr` even if it's part of a
-    // short-circuiting condition and thus might get skipped.
-    result.(NotExpr).getOperand() = sink.asExpr()
-    or
-    // Taint postfix and prefix crement operations when their operand is tainted.
-    result.(CrementOperation).getAnOperand() = sink.asExpr()
-    or
-    // Taint `e1 += e2`, `e &= e2` and friends when `e1` or `e2` is tainted.
-    result.(AssignOperation).getAnOperand() = sink.asExpr()
-    or
-    result =
-      sink.asOperand()
-          .(SideEffectOperand)
-          .getUse()
-          .(ReadSideEffectInstruction)
-          .getArgumentDef()
-          .getUnconvertedResultExpression()
-  }
-
-  /**
-   * Step to return value of a modeled function when an input taints the
-   * dereference of the return value.
-   */
-  cached
-  predicate additionalTaintStep(DataFlow::Node n1, DataFlow::Node n2) {
-    exists(CallInstruction call, Function func, FunctionInput modelIn, FunctionOutput modelOut |
-      n1.asOperand() = callInput(call, modelIn) and
-      (
-        func.(TaintFunction).hasTaintFlow(modelIn, modelOut)
-        or
-        func.(DataFlowFunction).hasDataFlow(modelIn, modelOut)
-      ) and
-      call.getStaticCallTarget() = func and
-      modelOut.isReturnValueDeref() and
-      call = n2.asInstruction()
-    )
-  }
-}
-
-private import Cached
-
-/**
- * Holds if `tainted` may contain taint from `source`.
- *
- * A tainted expression is either directly user input, or is
- * computed from user input in a way that users can probably
- * control the exact output of the computation.
- *
- * This doesn't include data flow through global variables.
- * If you need that you must call `taintedIncludingGlobalVars`.
- */
-cached
-predicate tainted(Expr source, Element tainted) {
-  exists(DefaultTaintTrackingCfg cfg, DataFlow::Node sink |
-    cfg.hasFlow(getNodeForSource(source), sink) and
-    tainted = adjustedSink(sink)
-  )
-}
-
-/**
- * Holds if `tainted` may contain taint from `source`, where the taint passed
- * through a global variable named `globalVar`.
- *
- * A tainted expression is either directly user input, or is
- * computed from user input in a way that users can probably
- * control the exact output of the computation.
- *
- * This version gives the same results as tainted but also includes
- * data flow through global variables.
- *
- * The parameter `globalVar` is the qualified name of the last global variable
- * used to move the value from source to tainted. If the taint did not pass
- * through a global variable, then `globalVar = ""`.
- */
-cached
-predicate taintedIncludingGlobalVars(Expr source, Element tainted, string globalVar) {
-  tainted(source, tainted) and
-  globalVar = ""
-  or
-  exists(
-    ToGlobalVarTaintTrackingCfg toCfg, FromGlobalVarTaintTrackingCfg fromCfg,
-    DataFlow::VariableNode variableNode, GlobalOrNamespaceVariable global, DataFlow::Node sink
-  |
-    global = variableNode.getVariable() and
-    toCfg.hasFlow(getNodeForSource(source), variableNode) and
-    fromCfg.hasFlow(variableNode, sink) and
-    tainted = adjustedSink(sink) and
-    global = globalVarFromId(globalVar)
-  )
-}
-
-/**
- * Gets the global variable whose qualified name is `id`. Use this predicate
- * together with `taintedIncludingGlobalVars`. Example:
- *
- * ```
- * exists(string varName |
- *   taintedIncludingGlobalVars(source, tainted, varName) and
- *   var = globalVarFromId(varName)
- * )
- * ```
- */
-GlobalOrNamespaceVariable globalVarFromId(string id) { id = result.getQualifiedName() }
-
-/**
- * Provides definitions for augmenting source/sink pairs with data-flow paths
- * between them. From a `@kind path-problem` query, import this module in the
- * global scope, extend `TaintTrackingConfiguration`, and use `taintedWithPath`
- * in place of `tainted`.
- *
- * Importing this module will also import the query predicates that contain the
- * taint paths.
- */
-module TaintedWithPath {
-  private newtype TSingleton = MkSingleton()
-
-  /**
-   * A taint-tracking configuration that matches sources and sinks in the same
-   * way as the `tainted` predicate.
-   *
-   * Override `isSink` and `taintThroughGlobals` as needed, but do not provide
-   * a characteristic predicate.
-   */
-  class TaintTrackingConfiguration extends TSingleton {
-    /** Override this to specify which elements are sources in this configuration. */
-    predicate isSource(Expr source) { exists(getNodeForSource(source)) }
-
-    /** Override this to specify which elements are sinks in this configuration. */
-    abstract predicate isSink(Element e);
-
-    /** Override this to specify which expressions are barriers in this configuration. */
-    predicate isBarrier(Expr e) { nodeIsBarrier(getNodeForExpr(e)) }
-
-    /**
-     * Override this predicate to `any()` to allow taint to flow through global
-     * variables.
-     */
-    predicate taintThroughGlobals() { none() }
-
-    /** Gets a textual representation of this element. */
-    string toString() { result = "TaintTrackingConfiguration" }
-  }
-
-  private class AdjustedConfiguration extends TaintTracking3::Configuration {
-    AdjustedConfiguration() { this = "AdjustedConfiguration" }
-
-    override predicate isSource(DataFlow::Node source) {
-      exists(TaintTrackingConfiguration cfg, Expr e |
-        cfg.isSource(e) and source = getNodeForExpr(e)
-      )
-    }
-
-    override predicate isSink(DataFlow::Node sink) {
-      exists(TaintTrackingConfiguration cfg | cfg.isSink(adjustedSink(sink)))
-    }
-
-    override predicate isAdditionalTaintStep(DataFlow::Node n1, DataFlow::Node n2) {
-      // Steps into and out of global variables
-      exists(TaintTrackingConfiguration cfg | cfg.taintThroughGlobals() |
-        writesVariable(n1.asInstruction(), n2.asVariable().(GlobalOrNamespaceVariable))
-        or
-        readsVariable(n2.asInstruction(), n1.asVariable().(GlobalOrNamespaceVariable))
-      )
-      or
-      additionalTaintStep(n1, n2)
-    }
-
-    override predicate isSanitizer(DataFlow::Node node) {
-      exists(TaintTrackingConfiguration cfg, Expr e | cfg.isBarrier(e) and node = getNodeForExpr(e))
-    }
-
-    override predicate isSanitizerIn(DataFlow::Node node) { nodeIsBarrierIn(node) }
-  }
-
-  /*
-   * A sink `Element` may map to multiple `DataFlowX::PathNode`s via (the
-   * inverse of) `adjustedSink`. For example, an `Expr` maps to all its
-   * conversions, and a `Variable` maps to all loads and stores from it. Because
-   * the path node is part of the tuple that constitutes the alert, this leads
-   * to duplicate alerts.
-   *
-   * To avoid showing duplicates, we edit the graph to replace the final node
-   * coming from the data-flow library with a node that matches exactly the
-   * `Element` sink that's requested.
-   *
-   * The same is done for sources.
-   */
-
-  private newtype TPathNode =
-    TWrapPathNode(DataFlow3::PathNode n) or
-    // There's a single newtype constructor for both sources and sinks since
-    // that makes it easiest to deal with the case where source = sink.
-    TEndpointPathNode(Element e) {
-      exists(AdjustedConfiguration cfg, DataFlow3::Node sourceNode, DataFlow3::Node sinkNode |
-        cfg.hasFlow(sourceNode, sinkNode)
-      |
-        sourceNode = getNodeForExpr(e) and
-        exists(TaintTrackingConfiguration ttCfg | ttCfg.isSource(e))
-        or
-        e = adjustedSink(sinkNode) and
-        exists(TaintTrackingConfiguration ttCfg | ttCfg.isSink(e))
-      )
-    }
-
-  /** An opaque type used for the nodes of a data-flow path. */
-  class PathNode extends TPathNode {
-    /** Gets a textual representation of this element. */
-    string toString() { none() }
-
-    /**
-     * Holds if this element is at the specified location.
-     * The location spans column `startcolumn` of line `startline` to
-     * column `endcolumn` of line `endline` in file `filepath`.
-     * For more information, see
-     * [Locations](https://codeql.github.com/docs/writing-codeql-queries/providing-locations-in-codeql-queries/).
-     */
-    predicate hasLocationInfo(
-      string filepath, int startline, int startcolumn, int endline, int endcolumn
-    ) {
-      none()
-    }
-  }
-
-  /**
-   * INTERNAL: Do not use.
-   */
-  module Private {
-    /** Gets a predecessor `PathNode` of `pathNode`, if any. */
-    PathNode getAPredecessor(PathNode pathNode) { edges(result, pathNode) }
-
-    /** Gets the element that `pathNode` wraps, if any. */
-    Element getElementFromPathNode(PathNode pathNode) {
-      exists(DataFlow::Node node | node = pathNode.(WrapPathNode).inner().getNode() |
-        result = node.asInstruction().getAst()
-        or
-        result = node.asOperand().getDef().getAst()
-      )
-      or
-      result = pathNode.(EndpointPathNode).inner()
-    }
-  }
-
-  private class WrapPathNode extends PathNode, TWrapPathNode {
-    DataFlow3::PathNode inner() { this = TWrapPathNode(result) }
-
-    override string toString() { result = this.inner().toString() }
-
-    override predicate hasLocationInfo(
-      string filepath, int startline, int startcolumn, int endline, int endcolumn
-    ) {
-      this.inner().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
-    }
-  }
-
-  private class EndpointPathNode extends PathNode, TEndpointPathNode {
-    Expr inner() { this = TEndpointPathNode(result) }
-
-    override string toString() { result = this.inner().toString() }
-
-    override predicate hasLocationInfo(
-      string filepath, int startline, int startcolumn, int endline, int endcolumn
-    ) {
-      this.inner()
-          .getLocation()
-          .hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
-    }
-  }
-
-  /** A PathNode whose `Element` is a source. It may also be a sink. */
-  private class InitialPathNode extends EndpointPathNode {
-    InitialPathNode() { exists(TaintTrackingConfiguration cfg | cfg.isSource(this.inner())) }
-  }
-
-  /** A PathNode whose `Element` is a sink. It may also be a source. */
-  private class FinalPathNode extends EndpointPathNode {
-    FinalPathNode() { exists(TaintTrackingConfiguration cfg | cfg.isSink(this.inner())) }
-  }
-
-  /** Holds if `(a,b)` is an edge in the graph of data flow path explanations. */
-  query predicate edges(PathNode a, PathNode b) {
-    DataFlow3::PathGraph::edges(a.(WrapPathNode).inner(), b.(WrapPathNode).inner())
-    or
-    // To avoid showing trivial-looking steps, we _replace_ the last node instead
-    // of adding an edge out of it.
-    exists(WrapPathNode sinkNode |
-      DataFlow3::PathGraph::edges(a.(WrapPathNode).inner(), sinkNode.inner()) and
-      b.(FinalPathNode).inner() = adjustedSink(sinkNode.inner().getNode())
-    )
-    or
-    // Same for the first node
-    exists(WrapPathNode sourceNode |
-      DataFlow3::PathGraph::edges(sourceNode.inner(), b.(WrapPathNode).inner()) and
-      sourceNode.inner().getNode() = getNodeForExpr(a.(InitialPathNode).inner())
-    )
-    or
-    // Finally, handle the case where the path goes directly from a source to a
-    // sink, meaning that they both need to be translated.
-    exists(WrapPathNode sinkNode, WrapPathNode sourceNode |
-      DataFlow3::PathGraph::edges(sourceNode.inner(), sinkNode.inner()) and
-      sourceNode.inner().getNode() = getNodeForExpr(a.(InitialPathNode).inner()) and
-      b.(FinalPathNode).inner() = adjustedSink(sinkNode.inner().getNode())
-    )
-  }
-
-  /**
-   * Holds if there is flow from `arg` to `out` across a call that can by summarized by the flow
-   * from `par` to `ret` within it, in the graph of data flow path explanations.
-   */
-  query predicate subpaths(PathNode arg, PathNode par, PathNode ret, PathNode out) {
-    DataFlow3::PathGraph::subpaths(arg.(WrapPathNode).inner(), par.(WrapPathNode).inner(),
-      ret.(WrapPathNode).inner(), out.(WrapPathNode).inner())
-    or
-    // To avoid showing trivial-looking steps, we _replace_ the last node instead
-    // of adding an edge out of it.
-    exists(WrapPathNode sinkNode |
-      DataFlow3::PathGraph::subpaths(arg.(WrapPathNode).inner(), par.(WrapPathNode).inner(),
-        ret.(WrapPathNode).inner(), sinkNode.inner()) and
-      out.(FinalPathNode).inner() = adjustedSink(sinkNode.inner().getNode())
-    )
-    or
-    // Same for the first node
-    exists(WrapPathNode sourceNode |
-      DataFlow3::PathGraph::subpaths(sourceNode.inner(), par.(WrapPathNode).inner(),
-        ret.(WrapPathNode).inner(), out.(WrapPathNode).inner()) and
-      sourceNode.inner().getNode() = getNodeForExpr(arg.(InitialPathNode).inner())
-    )
-    or
-    // Finally, handle the case where the path goes directly from a source to a
-    // sink, meaning that they both need to be translated.
-    exists(WrapPathNode sinkNode, WrapPathNode sourceNode |
-      DataFlow3::PathGraph::subpaths(sourceNode.inner(), par.(WrapPathNode).inner(),
-        ret.(WrapPathNode).inner(), sinkNode.inner()) and
-      sourceNode.inner().getNode() = getNodeForExpr(arg.(InitialPathNode).inner()) and
-      out.(FinalPathNode).inner() = adjustedSink(sinkNode.inner().getNode())
-    )
-  }
-
-  /** Holds if `n` is a node in the graph of data flow path explanations. */
-  query predicate nodes(PathNode n, string key, string val) {
-    key = "semmle.label" and val = n.toString()
-  }
-
-  /**
-   * Holds if `tainted` may contain taint from `source`, where `sourceNode` and
-   * `sinkNode` are the corresponding `PathNode`s that can be used in a query
-   * to provide path explanations. Extend `TaintTrackingConfiguration` to use
-   * this predicate.
-   *
-   * A tainted expression is either directly user input, or is computed from
-   * user input in a way that users can probably control the exact output of
-   * the computation.
-   */
-  predicate taintedWithPath(Expr source, Element tainted, PathNode sourceNode, PathNode sinkNode) {
-    exists(AdjustedConfiguration cfg, DataFlow3::Node flowSource, DataFlow3::Node flowSink |
-      source = sourceNode.(InitialPathNode).inner() and
-      flowSource = getNodeForExpr(source) and
-      cfg.hasFlow(flowSource, flowSink) and
-      tainted = adjustedSink(flowSink) and
-      tainted = sinkNode.(FinalPathNode).inner()
-    )
-  }
-
-  private predicate isGlobalVariablePathNode(WrapPathNode n) {
-    n.inner().getNode().asVariable() instanceof GlobalOrNamespaceVariable
-  }
-
-  private predicate edgesWithoutGlobals(PathNode a, PathNode b) {
-    edges(a, b) and
-    not isGlobalVariablePathNode(a) and
-    not isGlobalVariablePathNode(b)
-  }
-
-  /**
-   * Holds if `tainted` can be reached from a taint source without passing
-   * through a global variable.
-   */
-  predicate taintedWithoutGlobals(Element tainted) {
-    exists(AdjustedConfiguration cfg, PathNode sourceNode, FinalPathNode sinkNode |
-      cfg.isSource(sourceNode.(WrapPathNode).inner().getNode()) and
-      edgesWithoutGlobals+(sourceNode, sinkNode) and
-      tainted = sinkNode.inner()
-    )
-  }
-}

cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/TaintTrackingUtil.qll

@@ -169,11 +169,19 @@ predicate defaultTaintSanitizer(DataFlow::Node node) { none() }
  */
 predicate modeledTaintStep(Operand nodeIn, Instruction nodeOut) {
   exists(CallInstruction call, TaintFunction func, FunctionInput modelIn, FunctionOutput modelOut |
+    (
+      nodeIn = callInput(call, modelIn)
+      or
+      exists(int n |
+        modelIn.isParameterDerefOrQualifierObject(n) and
+        if n = -1
+        then nodeIn = callInput(call, any(InQualifierObject inQualifier))
+        else nodeIn = callInput(call, any(InParameter inParam | inParam.getIndex() = n))
+      )
+    ) and
+    nodeOut = callOutput(call, modelOut) and
     call.getStaticCallTarget() = func and
     func.hasTaintFlow(modelIn, modelOut)
-  |
-    nodeIn = callInput(call, modelIn) and
-    nodeOut = callOutput(call, modelOut)
   )
   or
   // Taint flow from one argument to another and data flow from an argument to a

cpp/ql/lib/semmle/code/cpp/ir/implementation/Opcode.qll

@@ -30,7 +30,6 @@ private newtype TOpcode =
   TNegate() or
   TShiftLeft() or
   TShiftRight() or
-  TUnsignedShiftRight() or
   TBitAnd() or
   TBitOr() or
   TBitXor() or
@@ -653,15 +652,6 @@ module Opcode {
     final override string toString() { result = "ShiftRight" }
   }
 
-  /**
-   * The `Opcode` for a `UnsignedShiftRightInstruction`.
-   *
-   * See the `UnsignedShiftRightInstruction` documentation for more details.
-   */
-  class UnsignedShiftRight extends BinaryBitwiseOpcode, TUnsignedShiftRight {
-    final override string toString() { result = "UnsignedShiftRight" }
-  }
-
   /**
    * The `Opcode` for a `BitAndInstruction`.
    *

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/Instruction.qll

@@ -1204,17 +1204,6 @@ class ShiftRightInstruction extends BinaryBitwiseInstruction {
   ShiftRightInstruction() { this.getOpcode() instanceof Opcode::ShiftRight }
 }
 
-/**
- * An instruction that shifts its left operand to the right by the number of bits specified by its
- * right operand.
- *
- * Both operands must have an integer type. The result has the same type as the left operand.
- * The leftmost bits are zero-filled.
- */
-class UnsignedShiftRightInstruction extends BinaryBitwiseInstruction {
-  UnsignedShiftRightInstruction() { this.getOpcode() instanceof Opcode::UnsignedShiftRight }
-}
-
 /**
  * An instruction that performs a binary arithmetic operation involving at least one pointer
  * operand.

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/Operand.qll

@@ -45,7 +45,7 @@ class Operand extends TStageOperand {
       this = reusedPhiOperand(use, def, predecessorBlock, _)
     )
     or
-    this = chiOperand(_, _)
+    exists(Instruction use | this = chiOperand(use, _))
   }
 
   /** Gets a textual representation of this element. */
@@ -412,9 +412,6 @@ class CallTargetOperand extends RegisterOperand {
  */
 class ArgumentOperand extends RegisterOperand {
   override ArgumentOperandTag tag;
-
-  /** Gets the `CallInstruction` for which this is an argument. */
-  CallInstruction getCall() { result.getAnArgumentOperand() = this }
 }
 
 /**

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/internal/SSAConstruction.qll

@@ -329,12 +329,12 @@ private module Cached {
   cached
   Instruction getChiInstructionTotalOperand(ChiInstruction chiInstr) {
     exists(
-      Alias::VirtualVariable vvar, OldInstruction oldInstr, OldBlock defBlock, int defRank,
-      int defOffset, OldBlock useBlock, int useRank
+      Alias::VirtualVariable vvar, OldInstruction oldInstr, Alias::MemoryLocation defLocation,
+      OldBlock defBlock, int defRank, int defOffset, OldBlock useBlock, int useRank
     |
       chiInstr = getChi(oldInstr) and
       vvar = Alias::getResultMemoryLocation(oldInstr).getVirtualVariable() and
-      hasDefinitionAtRank(vvar, _, defBlock, defRank, defOffset) and
+      hasDefinitionAtRank(vvar, defLocation, defBlock, defRank, defOffset) and
       hasUseAtRank(vvar, useBlock, useRank, oldInstr) and
       definitionReachesUse(vvar, defBlock, defRank, useBlock, useRank) and
       result = getDefinitionOrChiInstruction(defBlock, defOffset, vvar, _)