← Back
Home › Systems › CI/CD and developer tooling

sast

static code scanning

CodeQL, Semgrep

SystemTechniques · 9Primitives · 23 sast Alias analysiscompilers · medium: Decide whether two pointers may refer to the same memory (Andersen, Steensgaard, type-based) to enable optimizationsCall graph constructioncompilers · medium: Building call graphs with dynamic dispatch resolution (CHA, RTA)Dataflow analysiscompilers · medium: Compute a fact per program point (live variables, reaching definitions, available expressions) by iterating transfer functions over the CFG to a fixed point.›Datalog evaluationcompilers · medium: Semi-naive bottom-up evaluation of recursive Datalog rulesIncremental parsingcompilers · medium: Reparse only the region an edit damaged and splice the new subtrees into the old tree, sharing everything else; O(edit) instead of O(file).›Linear-time regular expression matc…search-sort · medium: Match a regular expression in O(pattern x text) worst case by tracking all live parse positions at once, then cache the state sets as a lazily built DFA for speed.›Taint trackingsecurity · medium: Track untrusted sources to sensitive sinks through dataflowSSA formcompilers · low: Give every variable exactly one definition, merging at joins with phi functions; def-use becomes explicit and optimizations turn sparse and cheap.›Union-findgraphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›Control-flow graphcompilers · low: Split a linear instruction list into basic blocks and connect them by jumps; the graph every optimizer, SSA builder and dataflow pass walks.›Name resolutioncompilers · low: Bind every use of a name to its declaration with a scope stack, handling shadowing, hoisting and closure capture in one AST walk.›Recursive-descent parsingcompilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.›String interningdata-structures · low: Store each distinct string once and refer to it by idTree pattern matchingcompilers · low: Matching AST patterns with metavariablesTopological sortgraphs · low: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.›Strongly connected componentsgraphs · low: Tarjan/Kosaraju SCCs for cycle detection in dependency graphsB+ treestorage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.›Hash joinstorage · low: Build a hash table on the smaller input's join key and probe it with every row of the larger one; the linear-time workhorse for equi-joins.›Ropegraphics · low: A balanced tree of small string chunks with cached byte and newline counts, so seek, insert, delete and snapshot cost O(log n) instead of O(n).›Aho-Corasick multi-pattern matchingsearch-sort · low: Find all occurrences of many fixed patterns in one pass over the text, in time independent of the pattern count, using a trie with failure links.›SIMD substring searchsearch-sort · low: Find bytes or substrings by comparing 16-64 haystack positions per instruction against the needle's first and last byte, then verifying the rare candidates.›LRU and CLOCKsystems · low: LRU evicts the least recently used entry via hash map plus linked list; CLOCK approximates it with a reference bit, so hits take no lock.›Sanitizerssecurity · low: ASan/UBSan/TSan shadow memory and instrumentation to catch memory bugs+ 2 more techniques+ 7 more primitives

Similar systems

Share the most building blocks with this one.

type-checker 22 %formatter-linter 21 %compiler 17 %