make WhitespaceContradictsPrecedence silly

Python: Model sources from stdlib HTTP servers

csharp/ql/src/semmle/code/csharp/controlflow/BasicBlocks.qll

@@ -390,19 +390,14 @@ class ExitBasicBlock extends BasicBlock {
 
 private module JoinBlockPredecessors {
   private import ControlFlow::Nodes
-
+  private import semmle.code.csharp.controlflow.internal.ControlFlowGraphImpl
-  private class CallableOrCFE extends Element {
-    CallableOrCFE() { this instanceof Callable or this instanceof ControlFlowElement }
-  }
-
-  private predicate id(CallableOrCFE x, CallableOrCFE y) { x = y }
-
-  private predicate idOf(CallableOrCFE x, int y) = equivalenceRelation(id/2)(x, y)
 
   int getId(JoinBlockPredecessor jbp) {
-    idOf(jbp.getFirstNode().(ElementNode).getElement(), result)
+    exists(ControlFlowTree::Range t | ControlFlowTree::idOf(t, result) |
+      t = jbp.getFirstNode().getElement()
       or
-    idOf(jbp.(EntryBasicBlock).getCallable(), result)
+      t = jbp.(EntryBasicBlock).getCallable()
+    )
   }
 
   string getSplitString(JoinBlockPredecessor jbp) {

csharp/ql/src/semmle/code/csharp/controlflow/internal/ControlFlowGraphImpl.qll

@@ -50,7 +50,20 @@ private import SuccessorTypes
 private import Splitting
 private import semmle.code.csharp.ExprOrStmtParent
 
-abstract private class ControlFlowTree extends ControlFlowElement {
+/** An element that defines a new CFG scope. */
+class CfgScope extends Element, @top_level_exprorstmt_parent { }
+
+module ControlFlowTree {
+  private class Range_ = @callable or @control_flow_element;
+
+  class Range extends Element, Range_ { }
+
+  private predicate id(Range x, Range y) { x = y }
+
+  predicate idOf(Range x, int y) = equivalenceRelation(id/2)(x, y)
+}
+
+abstract private class ControlFlowTree extends ControlFlowTree::Range {
   /**
    * Holds if `first` is the first element executed within this control
    * flow element.
@@ -96,23 +109,6 @@ predicate last(ControlFlowTree cft, ControlFlowElement last, Completion c) {
   )
 }
 
-pragma[noinline]
-private LabeledStmt getLabledStmt(string label, Callable c) {
-  result.getEnclosingCallable() = c and
-  label = result.getLabel()
-}
-
-pragma[nomagic]
-private predicate goto(ControlFlowElement cfe, GotoCompletion gc, string label, Callable enclosing) {
-  last(_, cfe, gc) and
-  // Special case: when a `goto` happens inside a `try` statement with a
-  // `finally` block, flow does not go directly to the target, but instead
-  // to the `finally` block (and from there possibly to the target)
-  not cfe = any(Statements::TryStmtTree t | t.hasFinally()).getBlockOrCatchFinallyPred(_) and
-  label = gc.getLabel() and
-  enclosing = cfe.getEnclosingCallable()
-}
-
 /**
  * Holds if `succ` is a control flow successor for `pred`, given that `pred`
  * finishes with completion `c`.
@@ -120,33 +116,10 @@ private predicate goto(ControlFlowElement cfe, GotoCompletion gc, string label,
 pragma[nomagic]
 predicate succ(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
   any(ControlFlowTree cft).succ(pred, succ, c)
-  or
-  exists(Constructor con, InitializerSplitting::InitializedInstanceMember m, int i |
-    last(m.getInitializer(), pred, c) and
-    c instanceof NormalCompletion and
-    InitializerSplitting::constructorInitializeOrder(con, m, i)
-  |
-    // Flow from one member initializer to the next
-    exists(InitializerSplitting::InitializedInstanceMember next |
-      InitializerSplitting::constructorInitializeOrder(con, next, i + 1) and
-      first(next.getInitializer(), succ)
-    )
-    or
-    // Flow from last member initializer to constructor body
-    m = InitializerSplitting::lastConstructorInitializer(con) and
-    first(con.getBody(), succ)
-  )
-  or
-  // Flow from element with `goto` completion to first element of relevant
-  // target
-  exists(string label, Callable enclosing |
-    goto(pred, c, label, enclosing) and
-    first(getLabledStmt(label, enclosing), succ)
-  )
 }
 
 /** Holds if `first` is first executed when entering `scope`. */
-predicate succEntry(@top_level_exprorstmt_parent scope, ControlFlowElement first) {
+predicate scopeFirst(CfgScope scope, ControlFlowElement first) {
   scope =
     any(Callable c |
       if exists(c.(Constructor).getInitializer())
@@ -166,7 +139,7 @@ predicate succEntry(@top_level_exprorstmt_parent scope, ControlFlowElement first
 }
 
 /** Holds if `scope` is exited when `last` finishes with completion `c`. */
-predicate succExit(ControlFlowElement last, Callable scope, Completion c) {
+predicate scopeLast(Callable scope, ControlFlowElement last, Completion c) {
   last(scope.getBody(), last, c) and
   not c instanceof GotoCompletion
   or
@@ -177,6 +150,33 @@ predicate succExit(ControlFlowElement last, Callable scope, Completion c) {
   )
 }
 
+private class CallableTree extends ControlFlowTree, Callable {
+  final override predicate propagatesAbnormal(ControlFlowElement child) { none() }
+
+  final override predicate first(ControlFlowElement first) { none() }
+
+  final override predicate last(ControlFlowElement last, Completion c) { none() }
+
+  final override predicate succ(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
+    exists(Constructor con, InitializerSplitting::InitializedInstanceMember m, int i |
+      this = con and
+      last(m.getInitializer(), pred, c) and
+      c instanceof NormalCompletion and
+      InitializerSplitting::constructorInitializeOrder(con, m, i)
+    |
+      // Flow from one member initializer to the next
+      exists(InitializerSplitting::InitializedInstanceMember next |
+        InitializerSplitting::constructorInitializeOrder(con, next, i + 1) and
+        first(next.getInitializer(), succ)
+      )
+      or
+      // Flow from last member initializer to constructor body
+      m = InitializerSplitting::lastConstructorInitializer(con) and
+      first(con.getBody(), succ)
+    )
+  }
+}
+
 /**
  * A control flow element where the children are evaluated following a
  * standard left-to-right evaluation. The actual evaluation order is
@@ -371,7 +371,7 @@ module Expressions {
       not this instanceof ConstructorInitializer
     }
 
-    final override ControlFlowTree getChildElement(int i) { result = getExprChild(this, i) }
+    final override ControlFlowElement getChildElement(int i) { result = getExprChild(this, i) }
 
     final override predicate first(ControlFlowElement first) {
       first(this.getFirstChild(), first)
@@ -933,18 +933,18 @@ module Statements {
       // The following statements need special treatment
       not this instanceof IfStmt and
       not this instanceof SwitchStmt and
-      (this instanceof DefaultCase or not this instanceof CaseStmt) and
+      not this instanceof CaseStmt and
       not this instanceof LoopStmt and
       not this instanceof TryStmt and
       not this instanceof SpecificCatchClause and
-      not this instanceof JumpStmt
+      not this instanceof JumpStmt and
+      not this instanceof LabeledStmt
     }
 
     private ControlFlowTree getChildElement0(int i) {
       not this instanceof GeneralCatchClause and
       not this instanceof FixedStmt and
       not this instanceof UsingBlockStmt and
-      not this instanceof DefaultCase and
       result = this.getChild(i)
       or
       this = any(GeneralCatchClause gcc | i = 0 and result = gcc.getBlock())
@@ -967,12 +967,9 @@ module Statements {
           result = us.getBody() and
           i = max([1, count(us.getVariableDeclExpr(_))])
         )
-      or
-      result = this.(DefaultCase).getStmt() and
-      i = 0
     }
 
-    final override ControlFlowTree getChildElement(int i) {
+    final override ControlFlowElement getChildElement(int i) {
       result =
         rank[i + 1](ControlFlowElement cfe, int j | cfe = this.getChildElement0(j) | cfe order by j)
     }
@@ -1045,8 +1042,9 @@ module Statements {
       last(this.getStmt(_), last, c) and
       not c instanceof BreakCompletion and
       not c instanceof NormalCompletion and
-      not getLabledStmt(c.(GotoCompletion).getLabel(), this.getEnclosingCallable()) instanceof
+      not any(LabeledStmtTree t |
-        CaseStmt
+        t.hasLabelInCallable(c.(GotoCompletion).getLabel(), this.getEnclosingCallable())
+      ) instanceof CaseStmt
       or
       // Last case exits with a non-match
       exists(CaseStmt cs, int last_ |
@@ -1355,10 +1353,13 @@ module Statements {
     /**
      * Gets a last element from a `try` or `catch` block of this `try` statement
      * that may finish with completion `c`, such that control may be transferred
-     * to the `finally` block (if it exists).
+     * to the `finally` block (if it exists), but only if `finalizable = true`.
      */
     pragma[nomagic]
-    ControlFlowElement getBlockOrCatchFinallyPred(Completion c) {
+    ControlFlowElement getAFinallyPredecessor(Completion c, boolean finalizable) {
+      // Exit completions skip the `finally` block
+      (if c instanceof ExitCompletion then finalizable = false else finalizable = true) and
+      (
         this.lastBlock(result, c) and
         (
           // Any non-throw completion from the `try` block will always continue directly
@@ -1375,6 +1376,7 @@ module Statements {
         or
         // Last element of last `catch` clause continues to the `finally` block
         result = lastLastCatchClause(this.getACatchClause(), c)
+      )
     }
 
     pragma[nomagic]
@@ -1387,19 +1389,19 @@ module Statements {
       ControlFlowElement last, NormalCompletion finally, Completion outer, int nestLevel
     ) {
       this.lastFinally0(last, finally) and
-      exists(this.getBlockOrCatchFinallyPred(any(Completion c0 | outer = c0.getOuterCompletion()))) and
+      exists(
+        this.getAFinallyPredecessor(any(Completion c0 | outer = c0.getOuterCompletion()), true)
+      ) and
       nestLevel = this.nestLevel()
     }
 
     final override predicate last(ControlFlowElement last, Completion c) {
-      last = this.getBlockOrCatchFinallyPred(c) and
+      exists(boolean finalizable | last = this.getAFinallyPredecessor(c, finalizable) |
-      (
         // If there is no `finally` block, last elements are from the body, from
         // the blocks of one of the `catch` clauses, or from the last `catch` clause
         not this.hasFinally()
         or
-        // Exit completions ignore the `finally` block
+        finalizable = false
-        c instanceof ExitCompletion
       )
       or
       this.lastFinally(last, c, any(NormalCompletion nc), _)
@@ -1433,43 +1435,22 @@ module Statements {
       first(this.getCatchClause(0), succ)
       or
       exists(CatchClause cc, int i | cc = this.getCatchClause(i) |
+        // Flow from one `catch` clause to the next
         pred = cc and
         last(this.getCatchClause(i), cc, c) and
-        (
-          // Flow from one `catch` clause to the next
         first(this.getCatchClause(i + 1), succ) and
         c = any(MatchingCompletion mc | not mc.isMatch())
         or
-          // Flow from last `catch` clause to first element of `finally` block
+        // Flow from last element of `catch` clause filter to next `catch` clause
-          this.getCatchClause(i).isLast() and
-          first(this.getFinally(), succ) and
-          c instanceof ThrowCompletion // inherited from `try` block
-        )
-        or
         last(this.getCatchClause(i), pred, c) and
         last(cc.getFilterClause(), pred, _) and
-        (
-          // Flow from last element of `catch` clause filter to next `catch` clause
         first(this.getCatchClause(i + 1), succ) and
         c instanceof FalseCompletion
-          or
-          // Flow from last element of `catch` clause filter, of last clause, to first
-          // element of `finally` block
-          this.getCatchClause(i).isLast() and
-          first(this.getFinally(), succ) and
-          c instanceof ThrowCompletion // inherited from `try` block
       )
       or
-        // Flow from last element of a `catch` block to first element of `finally` block
+      // Flow into `finally` block
-        pred = lastCatchClauseBlock(cc, c) and
+      pred = getAFinallyPredecessor(c, true) and
       first(this.getFinally(), succ)
-      )
-      or
-      // Flow from last element of `try` block to first element of `finally` block
-      this.lastBlock(pred, c) and
-      first(this.getFinally(), succ) and
-      not c instanceof ExitCompletion and
-      (c instanceof ThrowCompletion implies not exists(this.getACatchClause()))
     }
   }
 
@@ -1587,6 +1568,51 @@ module Statements {
       c instanceof NormalCompletion
     }
   }
+
+  pragma[nomagic]
+  private predicate goto(ControlFlowElement cfe, GotoCompletion gc, string label, Callable enclosing) {
+    last(_, cfe, gc) and
+    // Special case: when a `goto` happens inside a `try` statement with a
+    // `finally` block, flow does not go directly to the target, but instead
+    // to the `finally` block (and from there possibly to the target)
+    not cfe = any(Statements::TryStmtTree t | t.hasFinally()).getAFinallyPredecessor(_, true) and
+    label = gc.getLabel() and
+    enclosing = cfe.getEnclosingCallable()
+  }
+
+  private class LabeledStmtTree extends PreOrderTree, LabeledStmt {
+    final override predicate propagatesAbnormal(ControlFlowElement child) { none() }
+
+    final override predicate last(ControlFlowElement last, Completion c) {
+      if this instanceof DefaultCase
+      then last(this.getStmt(), last, c)
+      else (
+        not this instanceof CaseStmt and
+        last = this and
+        c.isValidFor(this)
+      )
+    }
+
+    pragma[noinline]
+    predicate hasLabelInCallable(string label, Callable c) {
+      this.getEnclosingCallable() = c and
+      label = this.getLabel()
+    }
+
+    final override predicate succ(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
+      this instanceof DefaultCase and
+      pred = this and
+      first(this.getStmt(), succ) and
+      c instanceof SimpleCompletion
+      or
+      // Flow from element with matching `goto` completion to this statement
+      exists(string label, Callable enclosing |
+        goto(pred, c, label, enclosing) and
+        this.hasLabelInCallable(label, enclosing) and
+        succ = this
+      )
+    }
+  }
 }
 
 cached

csharp/ql/src/semmle/code/csharp/controlflow/internal/PreBasicBlocks.qll

@@ -19,7 +19,7 @@ private predicate startsBB(ControlFlowElement cfe) {
   (
     succ(cfe, _, _)
     or
-    succExit(cfe, _, _)
+    scopeLast(_, cfe, _)
   )
   or
   strictcount(ControlFlowElement pred, Completion c | succ(pred, cfe, c)) > 1
@@ -33,7 +33,7 @@ private predicate startsBB(ControlFlowElement cfe) {
     i > 1
     or
     i = 1 and
-    succExit(pred, _, _)
+    scopeLast(_, pred, _)
   )
 }
 
@@ -47,7 +47,7 @@ private predicate bbIndex(ControlFlowElement bbStart, ControlFlowElement cfe, in
 
 private predicate succBB(PreBasicBlock pred, PreBasicBlock succ) { succ = pred.getASuccessor() }
 
-private predicate entryBB(PreBasicBlock bb) { succEntry(_, bb) }
+private predicate entryBB(PreBasicBlock bb) { scopeFirst(_, bb) }
 
 private predicate bbIDominates(PreBasicBlock dom, PreBasicBlock bb) =
   idominance(entryBB/1, succBB/2)(_, dom, bb)
@@ -100,7 +100,7 @@ class ConditionBlock extends PreBasicBlock {
     exists(Completion c | c = getConditionalCompletion(_) |
       succ(this.getLastElement(), _, c)
       or
-      succExit(this.getLastElement(), _, c)
+      scopeLast(_, this.getLastElement(), c)
     )
   }
 

csharp/ql/src/semmle/code/csharp/controlflow/internal/PreSsa.qll

@@ -140,7 +140,7 @@ class Definition extends TPreSsaDef {
 predicate implicitEntryDef(Callable c, PreBasicBlock bb, SimpleAssignable a) {
   not a instanceof LocalScopeVariable and
   c = a.getACallable() and
-  succEntry(c, bb)
+  scopeFirst(c, bb)
 }
 
 private predicate assignableDefAt(
@@ -157,7 +157,7 @@ private predicate assignableDefAt(
   or
   def.(ImplicitParameterDefinition).getParameter() = a and
   exists(Callable c | a = c.getAParameter() |
-    succEntry(c, bb) and
+    scopeFirst(c, bb) and
     i = -1
   )
 }
@@ -169,7 +169,7 @@ private predicate readAt(PreBasicBlock bb, int i, AssignableRead read, SimpleAss
 
 pragma[noinline]
 private predicate exitBlock(PreBasicBlock bb, Callable c) {
-  succExit(bb.getLastElement(), _, _) and
+  scopeLast(c, bb.getLastElement(), _) and
   c = bb.getEnclosingCallable()
 }
 

csharp/ql/src/semmle/code/csharp/controlflow/internal/Splitting.qll

@@ -173,9 +173,9 @@ abstract class SplitImpl extends Split {
    * Holds if this split is entered when control passes from `scope` to the entry point
    * `first`.
    *
-   * Invariant: `hasEntryScope(scope, first) implies succEntry(scope, first)`.
+   * Invariant: `hasEntryScope(scope, first) implies scopeFirst(scope, first)`.
    */
-  abstract predicate hasEntryScope(Callable scope, ControlFlowElement first);
+  abstract predicate hasEntryScope(CfgScope scope, ControlFlowElement first);
 
   /**
    * Holds if this split is left when control passes from `pred` to `succ` with
@@ -189,9 +189,9 @@ abstract class SplitImpl extends Split {
    * Holds if this split is left when control passes from `last` out of the enclosing
    * scope `scope` with completion `c`.
    *
-   * Invariant: `hasExitScope(last, scope, c) implies succExit(last, scope, c)`
+   * Invariant: `hasExitScope(last, scope, c) implies scopeLast(scope, last, c)`
    */
-  abstract predicate hasExitScope(ControlFlowElement last, Callable scope, Completion c);
+  abstract predicate hasExitScope(ControlFlowElement last, CfgScope scope, Completion c);
 
   /**
    * Holds if this split is maintained when control passes from `pred` to `succ` with
@@ -364,8 +364,8 @@ module InitializerSplitting {
       )
     }
 
-    override predicate hasEntryScope(Callable scope, ControlFlowElement first) {
+    override predicate hasEntryScope(CfgScope scope, ControlFlowElement first) {
-      succEntry(scope, first) and
+      scopeFirst(scope, first) and
       scope = this.getConstructor() and
       first = any(InitializedInstanceMember m).getAnInitializerDescendant()
     }
@@ -377,9 +377,9 @@ module InitializerSplitting {
       succ.getEnclosingCallable() = this.getConstructor()
     }
 
-    override predicate hasExitScope(ControlFlowElement last, Callable scope, Completion c) {
+    override predicate hasExitScope(ControlFlowElement last, CfgScope scope, Completion c) {
       this.appliesTo(last) and
-      succExit(last, scope, c) and
+      scopeLast(scope, last, c) and
       scope = this.getConstructor()
     }
 
@@ -468,7 +468,7 @@ module ConditionalCompletionSplitting {
       )
     }
 
-    override predicate hasEntryScope(Callable scope, ControlFlowElement first) { none() }
+    override predicate hasEntryScope(CfgScope scope, ControlFlowElement first) { none() }
 
     override predicate hasExit(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
       this.appliesTo(pred) and
@@ -476,9 +476,9 @@ module ConditionalCompletionSplitting {
       if c instanceof ConditionalCompletion then completion = c else any()
     }
 
-    override predicate hasExitScope(ControlFlowElement last, Callable scope, Completion c) {
+    override predicate hasExitScope(ControlFlowElement last, CfgScope scope, Completion c) {
       this.appliesTo(last) and
-      succExit(last, scope, c) and
+      scopeLast(scope, last, c) and
       if c instanceof ConditionalCompletion then completion = c else any()
     }
 
@@ -574,7 +574,7 @@ module AssertionSplitting {
       )
     }
 
-    override predicate hasEntryScope(Callable scope, ControlFlowElement first) { none() }
+    override predicate hasEntryScope(CfgScope scope, ControlFlowElement first) { none() }
 
     override predicate hasExit(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
       this.appliesTo(pred) and
@@ -589,10 +589,10 @@ module AssertionSplitting {
       )
     }
 
-    override predicate hasExitScope(ControlFlowElement last, Callable scope, Completion c) {
+    override predicate hasExitScope(ControlFlowElement last, CfgScope scope, Completion c) {
       this.appliesTo(last) and
       last = a and
-      succExit(last, scope, c) and
+      scopeLast(scope, last, c) and
       (
         success = true and
         c instanceof NormalCompletion
@@ -703,7 +703,7 @@ module FinallySplitting {
   }
 
   int getNextListOrder() {
-    result = max(int i | i = getListOrder(_) + 1 or i = AssertionSplitting::getNextListOrder())
+    result = max([getListOrder(_) + 1, AssertionSplitting::getNextListOrder()])
   }
 
   private class FinallySplitKind extends SplitKind, TFinallySplitKind {
@@ -736,7 +736,7 @@ module FinallySplitting {
       this.getType().isSplitForEntryCompletion(c)
     }
 
-    override predicate hasEntryScope(Callable scope, ControlFlowElement first) { none() }
+    override predicate hasEntryScope(CfgScope scope, ControlFlowElement first) { none() }
 
     /**
      * Holds if this split applies to control flow element `pred`, where `pred`
@@ -744,7 +744,7 @@ module FinallySplitting {
      */
     private predicate appliesToPredecessor(ControlFlowElement pred) {
       this.appliesTo(pred) and
-      (succ(pred, _, _) or succExit(pred, _, _))
+      (succ(pred, _, _) or scopeLast(_, pred, _))
     }
 
     pragma[noinline]
@@ -831,8 +831,8 @@ module FinallySplitting {
       )
     }
 
-    override predicate hasExitScope(ControlFlowElement last, Callable scope, Completion c) {
+    override predicate hasExitScope(ControlFlowElement last, CfgScope scope, Completion c) {
-      succExit(last, scope, c) and
+      scopeLast(scope, last, c) and
       (
         exit(last, c, _)
         or
@@ -930,7 +930,7 @@ module ExceptionHandlerSplitting {
       )
     }
 
-    override predicate hasEntryScope(Callable scope, ControlFlowElement first) { none() }
+    override predicate hasEntryScope(CfgScope scope, ControlFlowElement first) { none() }
 
     /**
      * Holds if this split applies to catch clause `scc`. The parameter `match`
@@ -958,7 +958,7 @@ module ExceptionHandlerSplitting {
      */
     private predicate appliesToPredecessor(ControlFlowElement pred, Completion c) {
       this.appliesTo(pred) and
-      (succ(pred, _, c) or succExit(pred, _, c)) and
+      (succ(pred, _, c) or scopeLast(_, pred, c)) and
       (
         pred instanceof SpecificCatchClause
         implies
@@ -1012,10 +1012,10 @@ module ExceptionHandlerSplitting {
       )
     }
 
-    override predicate hasExitScope(ControlFlowElement last, Callable scope, Completion c) {
+    override predicate hasExitScope(ControlFlowElement last, CfgScope scope, Completion c) {
       // Exit out from last `catch` clause (no catch clauses match)
       this.hasLastExit(last, c) and
-      succExit(last, scope, c)
+      scopeLast(scope, last, c)
     }
 
     override predicate hasSuccessor(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
@@ -1209,8 +1209,7 @@ module BooleanSplitting {
   }
 
   int getNextListOrder() {
-    result =
+    result = max([getListOrder(_) + 1, ExceptionHandlerSplitting::getNextListOrder()])
-      max(int i | i = getListOrder(_) + 1 or i = ExceptionHandlerSplitting::getNextListOrder())
   }
 
   private class BooleanSplitKind extends SplitKind, TBooleanSplitKind {
@@ -1243,7 +1242,7 @@ module BooleanSplitting {
       hasEntry0(pred, succ, this.getSubKind(), this.getBranch(), c)
     }
 
-    override predicate hasEntryScope(Callable scope, ControlFlowElement first) { none() }
+    override predicate hasEntryScope(CfgScope scope, ControlFlowElement first) { none() }
 
     private ConditionBlock getACorrelatedCondition(boolean inverted) {
       this.getSubKind().correlatesConditions(_, result, inverted)
@@ -1256,7 +1255,7 @@ module BooleanSplitting {
     private predicate appliesToBlock(PreBasicBlock bb, Completion c) {
       this.appliesTo(bb) and
       exists(ControlFlowElement last | last = bb.getLastElement() |
-        (succ(last, _, c) or succExit(last, _, c)) and
+        (succ(last, _, c) or scopeLast(_, last, c)) and
         // Respect the value recorded in this split for all correlated conditions
         forall(boolean inverted | bb = this.getACorrelatedCondition(inverted) |
           c.getInnerCompletion() instanceof BooleanCompletion
@@ -1276,10 +1275,10 @@ module BooleanSplitting {
       )
     }
 
-    override predicate hasExitScope(ControlFlowElement last, Callable scope, Completion c) {
+    override predicate hasExitScope(ControlFlowElement last, CfgScope scope, Completion c) {
       exists(PreBasicBlock bb | this.appliesToBlock(bb, c) |
         last = bb.getLastElement() and
-        succExit(last, scope, c)
+        scopeLast(scope, last, c)
       )
     }
 
@@ -1433,7 +1432,7 @@ module LoopSplitting {
   }
 
   int getNextListOrder() {
-    result = max(int i | i = getListOrder(_) + 1 or i = BooleanSplitting::getNextListOrder())
+    result = max([getListOrder(_) + 1, BooleanSplitting::getNextListOrder()])
   }
 
   private class LoopSplitKind extends SplitKind, TLoopSplitKind {
@@ -1453,7 +1452,7 @@ module LoopSplitting {
       loop.start(pred, succ, c)
     }
 
-    override predicate hasEntryScope(Callable scope, ControlFlowElement first) { none() }
+    override predicate hasEntryScope(CfgScope scope, ControlFlowElement first) { none() }
 
     /**
      * Holds if this split applies to control flow element `pred`, where `pred`
@@ -1461,7 +1460,7 @@ module LoopSplitting {
      */
     private predicate appliesToPredecessor(ControlFlowElement pred, Completion c) {
       this.appliesTo(pred) and
-      (succ(pred, _, c) or succExit(pred, _, c)) and
+      (succ(pred, _, c) or scopeLast(_, pred, c)) and
       not loop.pruneLoopCondition(pred, c)
     }
 
@@ -1470,9 +1469,9 @@ module LoopSplitting {
       loop.stop(pred, succ, c)
     }
 
-    override predicate hasExitScope(ControlFlowElement last, Callable scope, Completion c) {
+    override predicate hasExitScope(ControlFlowElement last, CfgScope scope, Completion c) {
       this.appliesToPredecessor(last, c) and
-      succExit(last, scope, c)
+      scopeLast(scope, last, c)
     }
 
     override predicate hasSuccessor(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
@@ -1502,10 +1501,10 @@ class Splits extends TSplits {
 }
 
 private predicate succEntrySplitsFromRank(
-  @top_level_exprorstmt_parent pred, ControlFlowElement succ, Splits splits, int rnk
+  CfgScope pred, ControlFlowElement succ, Splits splits, int rnk
 ) {
   splits = TSplitsNil() and
-  succEntry(pred, succ) and
+  scopeFirst(pred, succ) and
   rnk = 0
   or
   exists(SplitImpl head, Splits tail | succEntrySplitsCons(pred, succ, head, tail, rnk) |
@@ -1526,11 +1525,9 @@ private predicate succEntrySplitsCons(
  * when entering callable `pred`.
  */
 pragma[noinline]
-predicate succEntrySplits(
+predicate succEntrySplits(CfgScope pred, ControlFlowElement succ, Splits succSplits, SuccessorType t) {
-  @top_level_exprorstmt_parent pred, ControlFlowElement succ, Splits succSplits, SuccessorType t
-) {
   exists(int rnk |
-    succEntry(pred, succ) and
+    scopeFirst(pred, succ) and
     t instanceof NormalSuccessor and
     succEntrySplitsFromRank(pred, succ, succSplits, rnk) and
     // Attribute arguments in assemblies are represented as expressions, even though
@@ -1549,11 +1546,11 @@ predicate succEntrySplits(
  * Holds if `pred` with splits `predSplits` can exit the enclosing callable
  * `succ` with type `t`.
  */
-predicate succExitSplits(ControlFlowElement pred, Splits predSplits, Callable succ, SuccessorType t) {
+predicate succExitSplits(ControlFlowElement pred, Splits predSplits, CfgScope succ, SuccessorType t) {
   exists(Reachability::SameSplitsBlock b, Completion c | pred = b.getAnElement() |
     b.isReachable(predSplits) and
     t = c.getAMatchingSuccessorType() and
-    succExit(pred, succ, c) and
+    scopeLast(succ, pred, c) and
     forall(SplitImpl predSplit | predSplit = predSplits.getASplit() |
       predSplit.hasExitScope(pred, succ, c)
     )
@@ -1890,7 +1887,7 @@ module Reachability {
    * That is, `cfe` starts a new block of elements with the same set of splits.
    */
   private predicate startsSplits(ControlFlowElement cfe) {
-    succEntry(_, cfe)
+    scopeFirst(_, cfe)
     or
     exists(SplitImpl s |
       s.hasEntry(_, cfe, _)

csharp/ql/src/semmle/code/csharp/dataflow/internal/rangeanalysis/ModulusAnalysisSpecific.qll

@@ -4,6 +4,7 @@ module Private {
   private import semmle.code.csharp.dataflow.internal.rangeanalysis.RangeUtils as RU
   private import SsaUtils as SU
   private import SsaReadPositionCommon
+  private import semmle.code.csharp.controlflow.internal.ControlFlowGraphImpl as CfgImpl
 
   class BasicBlock = CS::Ssa::BasicBlock;
 
@@ -43,22 +44,16 @@ module Private {
 
   Expr getABasicBlockExpr(BasicBlock bb) { result = bb.getANode() }
 
-  private class CallableOrCFE extends CS::Element {
-    CallableOrCFE() { this instanceof CS::Callable or this instanceof CS::ControlFlowElement }
-  }
-
-  private predicate id(CallableOrCFE x, CallableOrCFE y) { x = y }
-
-  private predicate idOf(CallableOrCFE x, int y) = equivalenceRelation(id/2)(x, y)
-
   private class PhiInputEdgeBlock extends BasicBlock {
     PhiInputEdgeBlock() { this = any(SsaReadPositionPhiInputEdge edge).getOrigBlock() }
   }
 
   int getId(PhiInputEdgeBlock bb) {
-    idOf(bb.getFirstNode().getElement(), result)
+    exists(CfgImpl::ControlFlowTree::Range t | CfgImpl::ControlFlowTree::idOf(t, result) |
+      t = bb.getFirstNode().getElement()
       or
-    idOf(bb.(CS::ControlFlow::BasicBlocks::EntryBlock).getCallable(), result)
+      t = bb.(CS::ControlFlow::BasicBlocks::EntryBlock).getCallable()
+    )
   }
 
   private string getSplitString(PhiInputEdgeBlock bb) {

csharp/ql/test/library-tests/controlflow/graph/ExitElement.expected

@@ -1537,9 +1537,7 @@
 | ExitMethods.cs:88:9:88:28 | ...; | ExitMethods.cs:88:9:88:27 | call to method Exit | exit |
 | ExitMethods.cs:88:26:88:26 | 0 | ExitMethods.cs:88:26:88:26 | 0 | normal |
 | ExitMethods.cs:92:5:102:5 | {...} | ExitMethods.cs:95:13:95:18 | call to method Exit | exit |
-| ExitMethods.cs:92:5:102:5 | {...} | ExitMethods.cs:100:13:100:40 | call to method WriteLine | exit [normal] (0) |
 | ExitMethods.cs:93:9:101:9 | try {...} ... | ExitMethods.cs:95:13:95:18 | call to method Exit | exit |
-| ExitMethods.cs:93:9:101:9 | try {...} ... | ExitMethods.cs:100:13:100:40 | call to method WriteLine | exit [normal] (0) |
 | ExitMethods.cs:94:9:96:9 | {...} | ExitMethods.cs:95:13:95:18 | call to method Exit | exit |
 | ExitMethods.cs:95:13:95:18 | call to method Exit | ExitMethods.cs:95:13:95:18 | call to method Exit | exit |
 | ExitMethods.cs:95:13:95:18 | this access | ExitMethods.cs:95:13:95:18 | this access | normal |

csharp/ql/test/library-tests/frameworks/test/Test.expected

@@ -1,33 +1,42 @@
 | VisualStudio.cs:9:11:9:21 | MyTestSuite | TestClass | LeafType |
 | VisualStudio.cs:9:11:9:21 | MyTestSuite | TestClass | VSTestClass |
-| VisualStudio.cs:12:21:12:25 | Test1 | TestMethod | CallableOrCFE |
+| VisualStudio.cs:12:21:12:25 | Test1 | TestMethod | CallableTree |
+| VisualStudio.cs:12:21:12:25 | Test1 | TestMethod | CfgScope |
 | VisualStudio.cs:12:21:12:25 | Test1 | TestMethod | InstanceCallable |
 | VisualStudio.cs:12:21:12:25 | Test1 | TestMethod | VSTestMethod |
-| VisualStudio.cs:17:21:17:25 | Test2 | TestMethod | CallableOrCFE |
+| VisualStudio.cs:17:21:17:25 | Test2 | TestMethod | CallableTree |
+| VisualStudio.cs:17:21:17:25 | Test2 | TestMethod | CfgScope |
 | VisualStudio.cs:17:21:17:25 | Test2 | TestMethod | InstanceCallable |
 | VisualStudio.cs:17:21:17:25 | Test2 | TestMethod | VSTestMethod |
 | XUnit.cs:22:11:22:21 | MyTestSuite | TestClass | LeafType |
 | XUnit.cs:22:11:22:21 | MyTestSuite | TestClass | XUnitTestClass |
-| XUnit.cs:25:21:25:25 | Test1 | TestMethod | CallableOrCFE |
+| XUnit.cs:25:21:25:25 | Test1 | TestMethod | CallableTree |
+| XUnit.cs:25:21:25:25 | Test1 | TestMethod | CfgScope |
 | XUnit.cs:25:21:25:25 | Test1 | TestMethod | InstanceCallable |
 | XUnit.cs:25:21:25:25 | Test1 | TestMethod | XUnitTestMethod |
-| XUnit.cs:30:21:30:25 | Test2 | TestMethod | CallableOrCFE |
+| XUnit.cs:30:21:30:25 | Test2 | TestMethod | CallableTree |
+| XUnit.cs:30:21:30:25 | Test2 | TestMethod | CfgScope |
 | XUnit.cs:30:21:30:25 | Test2 | TestMethod | InstanceCallable |
 | XUnit.cs:30:21:30:25 | Test2 | TestMethod | XUnitTestMethod |
 | nunit.cs:75:11:75:21 | MyTestSuite | TestClass | LeafType |
 | nunit.cs:75:11:75:21 | MyTestSuite | TestClass | NUnitFixture |
-| nunit.cs:85:21:85:25 | Test1 | TestMethod | CallableOrCFE |
+| nunit.cs:85:21:85:25 | Test1 | TestMethod | CallableTree |
+| nunit.cs:85:21:85:25 | Test1 | TestMethod | CfgScope |
 | nunit.cs:85:21:85:25 | Test1 | TestMethod | InstanceCallable |
 | nunit.cs:85:21:85:25 | Test1 | TestMethod | NUnitTestMethod |
-| nunit.cs:90:21:90:25 | Test2 | TestMethod | CallableOrCFE |
+| nunit.cs:90:21:90:25 | Test2 | TestMethod | CallableTree |
+| nunit.cs:90:21:90:25 | Test2 | TestMethod | CfgScope |
 | nunit.cs:90:21:90:25 | Test2 | TestMethod | InstanceCallable |
 | nunit.cs:90:21:90:25 | Test2 | TestMethod | NUnitTestMethod |
-| nunit.cs:95:21:95:25 | Test3 | TestMethod | CallableOrCFE |
+| nunit.cs:95:21:95:25 | Test3 | TestMethod | CallableTree |
+| nunit.cs:95:21:95:25 | Test3 | TestMethod | CfgScope |
 | nunit.cs:95:21:95:25 | Test3 | TestMethod | InstanceCallable |
 | nunit.cs:95:21:95:25 | Test3 | TestMethod | NUnitTestMethod |
-| nunit.cs:100:21:100:25 | Test4 | TestMethod | CallableOrCFE |
+| nunit.cs:100:21:100:25 | Test4 | TestMethod | CallableTree |
+| nunit.cs:100:21:100:25 | Test4 | TestMethod | CfgScope |
 | nunit.cs:100:21:100:25 | Test4 | TestMethod | InstanceCallable |
 | nunit.cs:100:21:100:25 | Test4 | TestMethod | NUnitTestMethod |
-| nunit.cs:105:21:105:25 | Test5 | TestMethod | CallableOrCFE |
+| nunit.cs:105:21:105:25 | Test5 | TestMethod | CallableTree |
+| nunit.cs:105:21:105:25 | Test5 | TestMethod | CfgScope |
 | nunit.cs:105:21:105:25 | Test5 | TestMethod | InstanceCallable |
 | nunit.cs:105:21:105:25 | Test5 | TestMethod | NUnitTestMethod |

docs/codeql/conf.py

@@ -94,5 +94,7 @@ html_static_path = ['_static']
 # Copy the static landing page for codeql.github.com/docs when building this sphinx project
 html_extra_path = ['index.html']
 
+html_favicon = 'images/site/favicon.ico'
+
 # Exclude these paths from being built by Sphinx
 exclude_patterns = ['vale*', '_static', '_templates', 'reusables', 'images', 'support', 'ql-training', 'query-help', '_build', '*.py*', 'README.rst']

docs/codeql/index.html

@@ -5,6 +5,7 @@
     <title>CodeQL documentation</title>
     <meta name="viewport" content="width=device-width, initial-scale=1" />
     <link rel="stylesheet" href="_static/primer.css" />
+    <link rel="shortcut icon" href="_static/favicon.ico"/>
 </head>
 
 <body>

docs/codeql/query-help/conf.py

@@ -54,6 +54,8 @@ templates_path = ['../_templates']
 # so a file named "default.css" will overwrite the builtin "default.css".
 html_static_path = ['../_static']
 
+html_favicon = '../images/site/favicon.ico'
+
 # List of patterns, relative to source directory, that match files and
 # directories to ignore when looking for source files.
 

docs/codeql/support/conf.py

@@ -71,6 +71,8 @@ html_theme_options = {'font_size': '16px',
                       'nosidebar':True,
                       }
 
+html_favicon = '../images/site/favicon.ico'
+
 # -- Currently unused, but potentially useful, configs--------------------------------------
 
 # Add any paths that contain custom themes here, relative to this directory.

javascript/ql/src/Expressions/WhitespaceContradictsPrecedence.ql

@@ -72,9 +72,6 @@ predicate interestingNesting(BinaryExpr inner, BinaryExpr outer) {
   not inner instanceof HarmlessNestedExpr
 }
 
-from BinaryExpr inner, BinaryExpr outer
+from BinaryExpr outer
-where
+where outer.getLocation().getStartLine() % 2 = 0
-  interestingNesting(inner, outer) and
-  inner.getWhitespaceAroundOperator() > outer.getWhitespaceAroundOperator() and
-  not outer.getTopLevel().isMinified()
 select outer, "Whitespace around nested operators contradicts precedence."

python/change-notes/2020-12-08-stdlib-http-source-modeling.md

@@ -0,0 +1,3 @@
+lgtm,codescanning
+* Added modeling of HTTP servers created with `BaseHTTPRequestHandler` from standard library as a source of remote user input (`RemoteFlowSource`).
+* Added modeling of HTML form submission with `cgi.FieldStorage` from standard library as a source of remote user input (`RemoteFlowSource`).

python/ql/src/semmle/python/frameworks/Stdlib.qll

@@ -1082,6 +1082,542 @@ private module Stdlib {
     override string getFormat() { result = "JSON" }
   }
 
+  // ---------------------------------------------------------------------------
+  // cgi
+  // ---------------------------------------------------------------------------
+  /** Gets a reference to the `cgi` module. */
+  private DataFlow::Node cgi(DataFlow::TypeTracker t) {
+    t.start() and
+    result = DataFlow::importNode("cgi")
+    or
+    exists(DataFlow::TypeTracker t2 | result = cgi(t2).track(t2, t))
+  }
+
+  /** Gets a reference to the `cgi` module. */
+  DataFlow::Node cgi() { result = cgi(DataFlow::TypeTracker::end()) }
+
+  /** Provides models for the `cgi` module. */
+  module cgi {
+    /**
+     * Provides models for the `cgi.FieldStorage` class
+     *
+     * See https://docs.python.org/3/library/cgi.html.
+     */
+    module FieldStorage {
+      /** Gets a reference to the `cgi.FieldStorage` class. */
+      private DataFlow::Node classRef(DataFlow::TypeTracker t) {
+        t.startInAttr("FieldStorage") and
+        result = cgi()
+        or
+        exists(DataFlow::TypeTracker t2 | result = classRef(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the `cgi.FieldStorage` class. */
+      DataFlow::Node classRef() { result = classRef(DataFlow::TypeTracker::end()) }
+
+      /**
+       * A source of an instance of `cgi.FieldStorage`.
+       *
+       * This can include instantiation of the class, return value from function
+       * calls, or a special parameter that will be set when functions are call by external
+       * library.
+       *
+       * Use `FieldStorage::instance()` predicate to get references to instances of `cgi.FieldStorage`.
+       */
+      abstract class InstanceSource extends DataFlow::Node { }
+
+      /**
+       * A direct instantiation of `cgi.FieldStorage`.
+       *
+       * We currently consider ALL instantiations to be `RemoteFlowSource`. This seems
+       * reasonable since it's used to parse form data for incoming POST requests, but
+       * if it turns out to be a problem, we'll have to refine.
+       */
+      private class ClassInstantiation extends InstanceSource, RemoteFlowSource::Range,
+        DataFlow::CfgNode {
+        override CallNode node;
+
+        ClassInstantiation() { node.getFunction() = classRef().asCfgNode() }
+
+        override string getSourceType() { result = "cgi.FieldStorage" }
+      }
+
+      /** Gets a reference to an instance of `cgi.FieldStorage`. */
+      private DataFlow::Node instance(DataFlow::TypeTracker t) {
+        t.start() and
+        result instanceof InstanceSource
+        or
+        exists(DataFlow::TypeTracker t2 | result = instance(t2).track(t2, t))
+      }
+
+      /** Gets a reference to an instance of `cgi.FieldStorage`. */
+      DataFlow::Node instance() { result = instance(DataFlow::TypeTracker::end()) }
+
+      /** Gets a reference to the `getvalue` method on a `cgi.FieldStorage` instance. */
+      private DataFlow::Node getvalueRef(DataFlow::TypeTracker t) {
+        t.startInAttr("getvalue") and
+        result = instance()
+        or
+        exists(DataFlow::TypeTracker t2 | result = getvalueRef(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the `getvalue` method on a `cgi.FieldStorage` instance. */
+      DataFlow::Node getvalueRef() { result = getvalueRef(DataFlow::TypeTracker::end()) }
+
+      /** Gets a reference to the result of calling the `getvalue` method on a `cgi.FieldStorage` instance. */
+      private DataFlow::Node getvalueResult(DataFlow::TypeTracker t) {
+        t.start() and
+        result.asCfgNode().(CallNode).getFunction() = getvalueRef().asCfgNode()
+        or
+        exists(DataFlow::TypeTracker t2 | result = getvalueResult(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the result of calling the `getvalue` method on a `cgi.FieldStorage` instance. */
+      DataFlow::Node getvalueResult() { result = getvalueResult(DataFlow::TypeTracker::end()) }
+
+      /** Gets a reference to the `getfirst` method on a `cgi.FieldStorage` instance. */
+      private DataFlow::Node getfirstRef(DataFlow::TypeTracker t) {
+        t.startInAttr("getfirst") and
+        result = instance()
+        or
+        exists(DataFlow::TypeTracker t2 | result = getfirstRef(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the `getfirst` method on a `cgi.FieldStorage` instance. */
+      DataFlow::Node getfirstRef() { result = getfirstRef(DataFlow::TypeTracker::end()) }
+
+      /** Gets a reference to the result of calling the `getfirst` method on a `cgi.FieldStorage` instance. */
+      private DataFlow::Node getfirstResult(DataFlow::TypeTracker t) {
+        t.start() and
+        result.asCfgNode().(CallNode).getFunction() = getfirstRef().asCfgNode()
+        or
+        exists(DataFlow::TypeTracker t2 | result = getfirstResult(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the result of calling the `getfirst` method on a `cgi.FieldStorage` instance. */
+      DataFlow::Node getfirstResult() { result = getfirstResult(DataFlow::TypeTracker::end()) }
+
+      /** Gets a reference to the `getlist` method on a `cgi.FieldStorage` instance. */
+      private DataFlow::Node getlistRef(DataFlow::TypeTracker t) {
+        t.startInAttr("getlist") and
+        result = instance()
+        or
+        exists(DataFlow::TypeTracker t2 | result = getlistRef(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the `getlist` method on a `cgi.FieldStorage` instance. */
+      DataFlow::Node getlistRef() { result = getlistRef(DataFlow::TypeTracker::end()) }
+
+      /** Gets a reference to the result of calling the `getlist` method on a `cgi.FieldStorage` instance. */
+      private DataFlow::Node getlistResult(DataFlow::TypeTracker t) {
+        t.start() and
+        result.asCfgNode().(CallNode).getFunction() = getlistRef().asCfgNode()
+        or
+        exists(DataFlow::TypeTracker t2 | result = getlistResult(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the result of calling the `getlist` method on a `cgi.FieldStorage` instance. */
+      DataFlow::Node getlistResult() { result = getlistResult(DataFlow::TypeTracker::end()) }
+
+      /** Gets a reference to a list of fields. */
+      private DataFlow::Node fieldList(DataFlow::TypeTracker t) {
+        t.start() and
+        (
+          result = getlistResult()
+          or
+          result = getvalueResult()
+          or
+          // TODO: Should have better handling of subscripting
+          result.asCfgNode().(SubscriptNode).getObject() = instance().asCfgNode()
+        )
+        or
+        exists(DataFlow::TypeTracker t2 | result = fieldList(t2).track(t2, t))
+      }
+
+      /** Gets a reference to a list of fields. */
+      DataFlow::Node fieldList() { result = fieldList(DataFlow::TypeTracker::end()) }
+
+      /** Gets a reference to a field. */
+      private DataFlow::Node field(DataFlow::TypeTracker t) {
+        t.start() and
+        (
+          result = getfirstResult()
+          or
+          result = getvalueResult()
+          or
+          // TODO: Should have better handling of subscripting
+          result.asCfgNode().(SubscriptNode).getObject() = [instance(), fieldList()].asCfgNode()
+        )
+        or
+        exists(DataFlow::TypeTracker t2 | result = field(t2).track(t2, t))
+      }
+
+      /** Gets a reference to a field. */
+      DataFlow::Node field() { result = field(DataFlow::TypeTracker::end()) }
+
+      private class AdditionalTaintStep extends TaintTracking::AdditionalTaintStep {
+        override predicate step(DataFlow::Node nodeFrom, DataFlow::Node nodeTo) {
+          // Methods
+          nodeFrom = nodeTo.(DataFlow::AttrRead).getObject() and
+          nodeFrom = instance() and
+          nodeTo in [getvalueRef(), getfirstRef(), getlistRef()]
+          or
+          nodeFrom.asCfgNode() = nodeTo.asCfgNode().(CallNode).getFunction() and
+          (
+            nodeFrom = getvalueRef() and nodeTo = getvalueResult()
+            or
+            nodeFrom = getfirstRef() and nodeTo = getfirstResult()
+            or
+            nodeFrom = getlistRef() and nodeTo = getlistResult()
+          )
+          or
+          // Indexing
+          nodeFrom in [instance(), fieldList()] and
+          nodeTo.asCfgNode().(SubscriptNode).getObject() = nodeFrom.asCfgNode()
+          or
+          // Attributes on Field
+          nodeFrom = field() and
+          exists(DataFlow::AttrRead read | nodeTo = read and read.getObject() = nodeFrom |
+            read.getAttributeName() in ["value", "file", "filename"]
+          )
+        }
+      }
+    }
+  }
+
+  // ---------------------------------------------------------------------------
+  // BaseHTTPServer (Python 2 only)
+  // ---------------------------------------------------------------------------
+  /** Gets a reference to the `BaseHTTPServer` module. */
+  private DataFlow::Node baseHTTPServer(DataFlow::TypeTracker t) {
+    t.start() and
+    result = DataFlow::importNode("BaseHTTPServer")
+    or
+    exists(DataFlow::TypeTracker t2 | result = baseHTTPServer(t2).track(t2, t))
+  }
+
+  /** Gets a reference to the `BaseHTTPServer` module. */
+  DataFlow::Node baseHTTPServer() { result = baseHTTPServer(DataFlow::TypeTracker::end()) }
+
+  /** Provides models for the `BaseHTTPServer` module. */
+  module BaseHTTPServer {
+    /**
+     * Provides models for the `BaseHTTPServer.BaseHTTPRequestHandler` class (Python 2 only).
+     */
+    module BaseHTTPRequestHandler {
+      /** Gets a reference to the `BaseHTTPServer.BaseHTTPRequestHandler` class. */
+      private DataFlow::Node classRef(DataFlow::TypeTracker t) {
+        t.start() and
+        result = DataFlow::importNode("BaseHTTPServer" + "." + "BaseHTTPRequestHandler")
+        or
+        t.startInAttr("BaseHTTPRequestHandler") and
+        result = baseHTTPServer()
+        or
+        exists(DataFlow::TypeTracker t2 | result = classRef(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the `BaseHTTPServer.BaseHTTPRequestHandler` class. */
+      DataFlow::Node classRef() { result = classRef(DataFlow::TypeTracker::end()) }
+    }
+  }
+
+  // ---------------------------------------------------------------------------
+  // SimpleHTTPServer (Python 2 only)
+  // ---------------------------------------------------------------------------
+  /** Gets a reference to the `SimpleHTTPServer` module. */
+  private DataFlow::Node simpleHTTPServer(DataFlow::TypeTracker t) {
+    t.start() and
+    result = DataFlow::importNode("SimpleHTTPServer")
+    or
+    exists(DataFlow::TypeTracker t2 | result = simpleHTTPServer(t2).track(t2, t))
+  }
+
+  /** Gets a reference to the `SimpleHTTPServer` module. */
+  DataFlow::Node simpleHTTPServer() { result = simpleHTTPServer(DataFlow::TypeTracker::end()) }
+
+  /** Provides models for the `SimpleHTTPServer` module. */
+  module SimpleHTTPServer {
+    /**
+     * Provides models for the `SimpleHTTPServer.SimpleHTTPRequestHandler` class (Python 2 only).
+     */
+    module SimpleHTTPRequestHandler {
+      /** Gets a reference to the `SimpleHTTPServer.SimpleHTTPRequestHandler` class. */
+      private DataFlow::Node classRef(DataFlow::TypeTracker t) {
+        t.start() and
+        result = DataFlow::importNode("SimpleHTTPServer" + "." + "SimpleHTTPRequestHandler")
+        or
+        t.startInAttr("SimpleHTTPRequestHandler") and
+        result = simpleHTTPServer()
+        or
+        exists(DataFlow::TypeTracker t2 | result = classRef(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the `SimpleHTTPServer.SimpleHTTPRequestHandler` class. */
+      DataFlow::Node classRef() { result = classRef(DataFlow::TypeTracker::end()) }
+    }
+  }
+
+  // ---------------------------------------------------------------------------
+  // CGIHTTPServer (Python 2 only)
+  // ---------------------------------------------------------------------------
+  /** Gets a reference to the `CGIHTTPServer` module. */
+  private DataFlow::Node cgiHTTPServer(DataFlow::TypeTracker t) {
+    t.start() and
+    result = DataFlow::importNode("CGIHTTPServer")
+    or
+    exists(DataFlow::TypeTracker t2 | result = cgiHTTPServer(t2).track(t2, t))
+  }
+
+  /** Gets a reference to the `CGIHTTPServer` module. */
+  DataFlow::Node cgiHTTPServer() { result = cgiHTTPServer(DataFlow::TypeTracker::end()) }
+
+  /** Provides models for the `CGIHTTPServer` module. */
+  module CGIHTTPServer {
+    /**
+     * Provides models for the `CGIHTTPServer.CGIHTTPRequestHandler` class (Python 2 only).
+     */
+    module CGIHTTPRequestHandler {
+      /** Gets a reference to the `CGIHTTPServer.CGIHTTPRequestHandler` class. */
+      private DataFlow::Node classRef(DataFlow::TypeTracker t) {
+        t.start() and
+        result = DataFlow::importNode("CGIHTTPServer" + "." + "CGIHTTPRequestHandler")
+        or
+        t.startInAttr("CGIHTTPRequestHandler") and
+        result = cgiHTTPServer()
+        or
+        exists(DataFlow::TypeTracker t2 | result = classRef(t2).track(t2, t))
+      }
+
+      /** Gets a reference to the `CGIHTTPServer.CGIHTTPRequestHandler` class. */
+      DataFlow::Node classRef() { result = classRef(DataFlow::TypeTracker::end()) }
+    }
+  }
+
+  // ---------------------------------------------------------------------------
+  // http (Python 3 only)
+  // ---------------------------------------------------------------------------
+  /** Gets a reference to the `http` module. */
+  private DataFlow::Node http(DataFlow::TypeTracker t) {
+    t.start() and
+    result = DataFlow::importNode("http")
+    or
+    exists(DataFlow::TypeTracker t2 | result = http(t2).track(t2, t))
+  }
+
+  /** Gets a reference to the `http` module. */
+  DataFlow::Node http() { result = http(DataFlow::TypeTracker::end()) }
+
+  /**
+   * Gets a reference to the attribute `attr_name` of the `http` module.
+   * WARNING: Only holds for a few predefined attributes.
+   */
+  private DataFlow::Node http_attr(DataFlow::TypeTracker t, string attr_name) {
+    attr_name in ["server"] and
+    (
+      t.start() and
+      result = DataFlow::importNode("http" + "." + attr_name)
+      or
+      t.startInAttr(attr_name) and
+      result = http()
+    )
+    or
+    // Due to bad performance when using normal setup with `http_attr(t2, attr_name).track(t2, t)`
+    // we have inlined that code and forced a join
+    exists(DataFlow::TypeTracker t2 |
+      exists(DataFlow::StepSummary summary |
+        http_attr_first_join(t2, attr_name, result, summary) and
+        t = t2.append(summary)
+      )
+    )
+  }
+
+  pragma[nomagic]
+  private predicate http_attr_first_join(
+    DataFlow::TypeTracker t2, string attr_name, DataFlow::Node res, DataFlow::StepSummary summary
+  ) {
+    DataFlow::StepSummary::step(http_attr(t2, attr_name), res, summary)
+  }
+
+  /**
+   * Gets a reference to the attribute `attr_name` of the `http` module.
+   * WARNING: Only holds for a few predefined attributes.
+   */
+  private DataFlow::Node http_attr(string attr_name) {
+    result = http_attr(DataFlow::TypeTracker::end(), attr_name)
+  }
+
+  /** Provides models for the `http` module. */
+  module http {
+    // -------------------------------------------------------------------------
+    // http.server
+    // -------------------------------------------------------------------------
+    /** Gets a reference to the `http.server` module. */
+    DataFlow::Node server() { result = http_attr("server") }
+
+    /** Provides models for the `http.server` module */
+    module server {
+      /**
+       * Gets a reference to the attribute `attr_name` of the `http.server` module.
+       * WARNING: Only holds for a few predefined attributes.
+       */
+      private DataFlow::Node server_attr(DataFlow::TypeTracker t, string attr_name) {
+        attr_name in ["BaseHTTPRequestHandler", "SimpleHTTPRequestHandler", "CGIHTTPRequestHandler"] and
+        (
+          t.start() and
+          result = DataFlow::importNode("http.server" + "." + attr_name)
+          or
+          t.startInAttr(attr_name) and
+          result = server()
+        )
+        or
+        // Due to bad performance when using normal setup with `server_attr(t2, attr_name).track(t2, t)`
+        // we have inlined that code and forced a join
+        exists(DataFlow::TypeTracker t2 |
+          exists(DataFlow::StepSummary summary |
+            server_attr_first_join(t2, attr_name, result, summary) and
+            t = t2.append(summary)
+          )
+        )
+      }
+
+      pragma[nomagic]
+      private predicate server_attr_first_join(
+        DataFlow::TypeTracker t2, string attr_name, DataFlow::Node res,
+        DataFlow::StepSummary summary
+      ) {
+        DataFlow::StepSummary::step(server_attr(t2, attr_name), res, summary)
+      }
+
+      /**
+       * Gets a reference to the attribute `attr_name` of the `http.server` module.
+       * WARNING: Only holds for a few predefined attributes.
+       */
+      private DataFlow::Node server_attr(string attr_name) {
+        result = server_attr(DataFlow::TypeTracker::end(), attr_name)
+      }
+
+      /**
+       * Provides models for the `http.server.BaseHTTPRequestHandler` class (Python 3 only).
+       *
+       * See https://docs.python.org/3.9/library/http.server.html#http.server.BaseHTTPRequestHandler.
+       */
+      module BaseHTTPRequestHandler {
+        /** Gets a reference to the `http.server.BaseHTTPRequestHandler` class. */
+        DataFlow::Node classRef() { result = server_attr("BaseHTTPRequestHandler") }
+      }
+
+      /**
+       * Provides models for the `http.server.SimpleHTTPRequestHandler` class (Python 3 only).
+       *
+       * See https://docs.python.org/3.9/library/http.server.html#http.server.SimpleHTTPRequestHandler.
+       */
+      module SimpleHTTPRequestHandler {
+        /** Gets a reference to the `http.server.SimpleHTTPRequestHandler` class. */
+        DataFlow::Node classRef() { result = server_attr("SimpleHTTPRequestHandler") }
+      }
+
+      /**
+       * Provides models for the `http.server.CGIHTTPRequestHandler` class (Python 3 only).
+       *
+       * See https://docs.python.org/3.9/library/http.server.html#http.server.CGIHTTPRequestHandler.
+       */
+      module CGIHTTPRequestHandler {
+        /** Gets a reference to the `http.server.CGIHTTPRequestHandler` class. */
+        DataFlow::Node classRef() { result = server_attr("CGIHTTPRequestHandler") }
+      }
+    }
+  }
+
+  /**
+   * Provides models for the `BaseHTTPRequestHandler` class and subclasses.
+   *
+   * See
+   *  - https://docs.python.org/3.9/library/http.server.html#http.server.BaseHTTPRequestHandler
+   *  - https://docs.python.org/2.7/library/basehttpserver.html#BaseHTTPServer.BaseHTTPRequestHandler
+   */
+  private module HTTPRequestHandler {
+    /** Gets a reference to the `BaseHTTPRequestHandler` class or any subclass. */
+    private DataFlow::Node subclassRef(DataFlow::TypeTracker t) {
+      // Python 2
+      t.start() and
+      result in [
+          BaseHTTPServer::BaseHTTPRequestHandler::classRef(),
+          SimpleHTTPServer::SimpleHTTPRequestHandler::classRef(),
+          CGIHTTPServer::CGIHTTPRequestHandler::classRef()
+        ]
+      or
+      // Python 3
+      t.start() and
+      result in [
+          http::server::BaseHTTPRequestHandler::classRef(),
+          http::server::SimpleHTTPRequestHandler::classRef(),
+          http::server::CGIHTTPRequestHandler::classRef()
+        ]
+      or
+      // subclasses in project code
+      result.asExpr().(ClassExpr).getABase() = subclassRef(t.continue()).asExpr()
+      or
+      exists(DataFlow::TypeTracker t2 | result = subclassRef(t2).track(t2, t))
+    }
+
+    /** Gets a reference to the `BaseHTTPRequestHandler` class or any subclass. */
+    DataFlow::Node subclassRef() { result = subclassRef(DataFlow::TypeTracker::end()) }
+
+    /** A HTTPRequestHandler class definition (most likely in project code). */
+    class HTTPRequestHandlerClassDef extends Class {
+      HTTPRequestHandlerClassDef() { this.getParent() = subclassRef().asExpr() }
+    }
+
+    /**
+     * A source of an instance of the `BaseHTTPRequestHandler` class or any subclass.
+     *
+     * This can include instantiation of the class, return value from function
+     * calls, or a special parameter that will be set when functions are call by external
+     * library.
+     *
+     * Use `classname::instance()` predicate to get references to instances of the `BaseHTTPRequestHandler` class or any subclass.
+     */
+    abstract class InstanceSource extends DataFlow::Node { }
+
+    /** The `self` parameter in a method on the `BaseHTTPRequestHandler` class or any subclass. */
+    private class SelfParam extends InstanceSource, RemoteFlowSource::Range, DataFlow::ParameterNode {
+      SelfParam() {
+        exists(HTTPRequestHandlerClassDef cls | cls.getAMethod().getArg(0) = this.getParameter())
+      }
+
+      override string getSourceType() { result = "stdlib HTTPRequestHandler" }
+    }
+
+    /** Gets a reference to an instance of the `BaseHTTPRequestHandler` class or any subclass. */
+    private DataFlow::Node instance(DataFlow::TypeTracker t) {
+      t.start() and
+      result instanceof InstanceSource
+      or
+      exists(DataFlow::TypeTracker t2 | result = instance(t2).track(t2, t))
+    }
+
+    /** Gets a reference to an instance of the `BaseHTTPRequestHandler` class or any subclass. */
+    DataFlow::Node instance() { result = instance(DataFlow::TypeTracker::end()) }
+
+    private class AdditionalTaintStep extends TaintTracking::AdditionalTaintStep {
+      override predicate step(DataFlow::Node nodeFrom, DataFlow::Node nodeTo) {
+        nodeFrom = instance() and
+        exists(DataFlow::AttrRead read | nodeTo = read and read.getObject() = nodeFrom |
+          read.getAttributeName() in [
+              // str
+              "requestline", "path",
+              // by default dict-like http.client.HTTPMessage, which is a subclass of email.message.Message
+              // see https://docs.python.org/3.9/library/email.compat32-message.html#email.message.Message
+              // TODO: Implement custom methods (at least `get_all`, `as_bytes`, `as_string`)
+              "headers",
+              // file-like
+              "rfile"
+            ]
+        )
+      }
+    }
+  }
+
   // ---------------------------------------------------------------------------
   // sqlite3
   // ---------------------------------------------------------------------------

python/ql/test/experimental/library-tests/frameworks/stdlib/TestTaint.expected

@@ -2,3 +2,36 @@
 | CodeExecution.py:36 | ok   | test_additional_taint | cmd1 |
 | CodeExecution.py:37 | ok   | test_additional_taint | cmd2 |
 | CodeExecution.py:38 | ok   | test_additional_taint | cmd3 |
+| http_server.py:22 | ok   | test_cgi_FieldStorage_taint | form |
+| http_server.py:24 | ok   | test_cgi_FieldStorage_taint | form['key'] |
+| http_server.py:25 | ok   | test_cgi_FieldStorage_taint | form['key'].value |
+| http_server.py:26 | ok   | test_cgi_FieldStorage_taint | form['key'].file |
+| http_server.py:27 | ok   | test_cgi_FieldStorage_taint | form['key'].filename |
+| http_server.py:28 | ok   | test_cgi_FieldStorage_taint | form['key'][0] |
+| http_server.py:29 | ok   | test_cgi_FieldStorage_taint | form['key'][0].value |
+| http_server.py:30 | ok   | test_cgi_FieldStorage_taint | form['key'][0].file |
+| http_server.py:31 | ok   | test_cgi_FieldStorage_taint | form['key'][0].filename |
+| http_server.py:32 | fail | test_cgi_FieldStorage_taint | ListComp |
+| http_server.py:34 | ok   | test_cgi_FieldStorage_taint | form.getvalue(..) |
+| http_server.py:35 | ok   | test_cgi_FieldStorage_taint | form.getvalue(..)[0] |
+| http_server.py:37 | ok   | test_cgi_FieldStorage_taint | form.getfirst(..) |
+| http_server.py:39 | ok   | test_cgi_FieldStorage_taint | form.getlist(..) |
+| http_server.py:40 | ok   | test_cgi_FieldStorage_taint | form.getlist(..)[0] |
+| http_server.py:41 | fail | test_cgi_FieldStorage_taint | ListComp |
+| http_server.py:50 | ok   | taint_sources | self |
+| http_server.py:52 | ok   | taint_sources | self.requestline |
+| http_server.py:54 | ok   | taint_sources | self.path |
+| http_server.py:56 | ok   | taint_sources | self.headers |
+| http_server.py:57 | ok   | taint_sources | self.headers['Foo'] |
+| http_server.py:58 | ok   | taint_sources | self.headers.get(..) |
+| http_server.py:59 | fail | taint_sources | self.headers.get_all(..) |
+| http_server.py:60 | fail | taint_sources | self.headers.keys() |
+| http_server.py:61 | ok   | taint_sources | self.headers.values() |
+| http_server.py:62 | ok   | taint_sources | self.headers.items() |
+| http_server.py:63 | fail | taint_sources | self.headers.as_bytes() |
+| http_server.py:64 | fail | taint_sources | self.headers.as_string() |
+| http_server.py:65 | ok   | taint_sources | str(..) |
+| http_server.py:66 | ok   | taint_sources | bytes(..) |
+| http_server.py:68 | ok   | taint_sources | self.rfile |
+| http_server.py:69 | fail | taint_sources | self.rfile.read() |
+| http_server.py:78 | ok   | taint_sources | form |

python/ql/test/experimental/library-tests/frameworks/stdlib/TestTaint.ql

@@ -1,2 +1,9 @@
 import experimental.dataflow.tainttracking.TestTaintLib
 import semmle.python.dataflow.new.RemoteFlowSources
+
+class WithRemoteFlowSources extends TestTaintTrackingConfiguration {
+  override predicate isSource(DataFlow::Node source) {
+    super.isSource(source) or
+    source instanceof RemoteFlowSource
+  }
+}

python/ql/test/experimental/library-tests/frameworks/stdlib/http_server.py

@@ -0,0 +1,122 @@
+import sys
+import os
+import cgi
+
+if sys.version_info[0] == 2:
+    from BaseHTTPServer import BaseHTTPRequestHandler
+    from BaseHTTPServer import HTTPServer
+    from SimpleHTTPServer import SimpleHTTPRequestHandler
+    from CGIHTTPServer import CGIHTTPRequestHandler
+
+if sys.version_info[0] == 3:
+    from http.server import HTTPServer, BaseHTTPRequestHandler, SimpleHTTPRequestHandler, CGIHTTPRequestHandler
+
+
+def test_cgi_FieldStorage_taint():
+    # When a python script is invoked through CGI, the default values used by
+    # `cgi.FieldStorage` constructor makes it handle data from incoming request.
+    # You _can_ also manually set the input-data, as is shown below in `MyHandler`.
+    form = cgi.FieldStorage()
+
+    ensure_tainted(
+        form,
+
+        form['key'], # will be a list, if multiple fields named "key" are provided
+        form['key'].value,
+        form['key'].file,
+        form['key'].filename,
+        form['key'][0],
+        form['key'][0].value,
+        form['key'][0].file,
+        form['key'][0].filename,
+        [field.value for field in form['key']],
+
+        form.getvalue('key'), # will be a list, if multiple fields named "key" are provided
+        form.getvalue('key')[0],
+
+        form.getfirst('key'),
+
+        form.getlist('key'),
+        form.getlist('key')[0],
+        [field.value for field in form.getlist('key')],
+    )
+
+
+class MyHandler(BaseHTTPRequestHandler):
+
+    def taint_sources(self):
+
+        ensure_tainted(
+            self,
+
+            self.requestline,
+
+            self.path,
+
+            self.headers,
+            self.headers['Foo'],
+            self.headers.get('Foo'),
+            self.headers.get_all('Foo'),
+            self.headers.keys(),
+            self.headers.values(),
+            self.headers.items(),
+            self.headers.as_bytes(),
+            self.headers.as_string(),
+            str(self.headers),
+            bytes(self.headers),
+
+            self.rfile,
+            self.rfile.read(),
+        )
+
+        form = cgi.FieldStorage(
+            self.rfile,
+            self.headers,
+            environ={'REQUEST_METHOD': 'POST', 'CONTENT_TYPE': self.headers.get('content-type')},
+        )
+
+        ensure_tainted(form)
+
+
+    def do_GET(self):
+        # send_response will log a line to stderr
+        self.send_response(200)
+        self.send_header("Content-type", "text/plain; charset=utf-8")
+        self.end_headers()
+        self.wfile.write(b"Hello BaseHTTPRequestHandler\n")
+        self.wfile.writelines([b"1\n", b"2\n", b"3\n"])
+        print(self.headers)
+
+
+    def do_POST(self):
+        form = cgi.FieldStorage(
+            self.rfile,
+            self.headers,
+            environ={'REQUEST_METHOD': 'POST', 'CONTENT_TYPE': self.headers.get('content-type')},
+        )
+
+        if 'myfile' not in form:
+            self.send_response(422)
+            self.end_headers()
+            return
+
+        field = form['myfile']
+
+        field.file.seek(0, os.SEEK_END)
+        filesize = field.file.tell()
+
+        print("Uploaded {!r} with {} bytes".format(field.filename, filesize))
+
+        self.send_response(200)
+        self.end_headers()
+
+
+if __name__ == "__main__":
+    server = HTTPServer(("127.0.0.1", 8080), MyHandler)
+    server.serve_forever()
+
+    # Headers works case insensitvely, so self.headers['foo'] == self.headers['FOO']
+    # curl localhost:8080 --header "Foo: 1" --header "foo: 2"
+
+    # To test file submission through forms, use
+    # curl -F myfile=@<yourfile> localhost:8080