(ns com.tailrecursion.blacktide.compiler.languages
"All compiler languages, in dependency order: JVM facts, source trees, graphs,
analyses and lexical control. Local nonterminals rebind during derivation;
qualified l/* types refer to another language here. Execution order lives in
com.tailrecursion.blacktide.compiler."
(:require [com.tailrecursion.nanopass :as np]
[com.tailrecursion.blacktide.compiler.languages :as-alias l]
[typed.clojure :as-alias t]))
;; Shared JVM facts and operations.
(np/deflanguage JVM
{Raw t/Any
Type (t/U ':unknown nil java.lang.Class)
Seed (t/HMap :mandatory {:hint Raw :var-meta (t/Map t/Any t/Any)} :complete? true)
Fact (t/HMap :mandatory {:hint Raw :var-meta (t/Map t/Any t/Any)
:type Type :primitive? t/Bool :hint-error (t/Option t/Str)} :complete? true)
Types (t/Vec Type)
Tags (t/Option (t/Vec Raw))
Mode (t/U ':method ':member ':field)
Protocol (t/HMap :mandatory {:class (t/Option java.lang.Class) :member (t/Option t/Sym)
:parameters (t/Vec java.lang.Class)} :complete? true)
Operation (t/U (t/HMap :mandatory {:op ':keyword :key t/Kw} :complete? true)
(t/HMap :mandatory {:op ':protocol :method Protocol} :complete? true)
(t/HMap :mandatory {:op ':direct :class java.lang.Class :parameters (t/Vec java.lang.Class)
:variadic? t/Bool :return java.lang.Class} :complete? true)
(t/HMap :mandatory {:op ':instanceof :class java.lang.Class} :complete? true)
(t/HMap :mandatory {:op ':adapt :class java.lang.Class} :complete? true)
(t/HMap :mandatory {:op ':constructor :class java.lang.Class :tags Tags} :complete? true)
(t/HMap :mandatory {:op ':static :class java.lang.Class :member t/Sym :tags Tags} :complete? true)
(t/HMap :mandatory {:op ':instance :class (t/Option java.lang.Class) :member t/Sym
:mode Mode :tags Tags} :complete? true)
(t/HMap :mandatory {:op ':static-field :class java.lang.Class :member t/Sym} :complete? true)
(t/HMap :mandatory {:op ':method-value :name t/Sym} :complete? true))
Syntax (t/HMap :mandatory {:operation Operation :operands (t/Vec Raw)} :complete? true)
Method (t/U java.lang.reflect.Method java.lang.reflect.Constructor)
Methods (t/Vec Method)
Conversion (t/HMap :mandatory {:type java.lang.Class :parameter? t/Bool} :complete? true)
Plan (t/HMap :mandatory {:operation Operation :conversions (t/Vec (t/Option Conversion))} :complete? true)
Selection (t/HMap :mandatory {:method (t/Option Method) :exact? t/Bool :tied? t/Bool} :complete? true)})
;; Source normalization: Bound -> Classified -> Assigned ->
;; Collections -> Prepared -> Ordered. Native is a restricted subtree.
(np/deflanguage Bound
{Raw t/Any
Forms (t/Vec Raw)
Site (t/HMap :mandatory {:form Raw :file (t/Option t/Str)
:line (t/Option t/Int) :column (t/Option t/Int)} :complete? true)
Jvm l/JVM-Fact
Local (t/HMap :mandatory {:id t/Sym :name t/Sym :mutable? t/Bool :external? t/Bool
:jvm Jvm} :complete? true)
Binding (t/HMap :mandatory {:local Local :init Expr} :complete? true)
Bindings (t/Vec Binding)
Assignment (t/HMap :mandatory {:target Local :value Expr} :complete? true)
Assignments (t/Vec Assignment)
RecurTarget (t/HMap :mandatory {:id t/Sym :bindings (t/Vec Local)} :complete? true)
CaseSpec (t/HMap :mandatory {:shift t/Int :mask t/Int :default t/Int
:tests (t/Map t/Int (t/HVec [Raw t/Int]))
:switch (t/U ':compact ':sparse)
:test (t/U ':int ':hash-equiv ':hash-identity)
:skip (t/Option (t/Set t/Int))} :complete? true)
CaseSyntax (t/HMap :mandatory {:selector Raw :arms Forms} :complete? true)
DispatchSyntax (t/HMap :mandatory {:value Raw :spec CaseSpec :arms Forms} :complete? true)
Exprs (t/Vec Expr)
CollectionKind (t/U ':vector ':map ':set)
Expr (t/HMap :mandatory {:site Site :jvm Jvm :node Node} :complete? true)
Node (t/U (t/HMap :mandatory {:op ':literal :value Raw} :complete? true)
(t/HMap :mandatory {:op ':local :local Local} :complete? true)
(t/HMap :mandatory {:op ':global :name t/Sym} :complete? true)
(t/HMap :mandatory {:op ':var :name t/Sym} :complete? true)
(t/HMap :mandatory {:op ':host :operation l/JVM-Operation :args (t/Vec Expr)} :complete? true)
(t/HMap :mandatory {:op ':invoke :function Expr :args (t/Vec Expr)} :complete? true)
(t/HMap :mandatory {:op ':collection :kind CollectionKind :items Exprs
:metadata (t/Option Expr)} :complete? true)
(t/HMap :mandatory {:op ':setq :pairs Assignments} :complete? true)
(t/HMap :mandatory {:op ':psetq :pairs Assignments} :complete? true)
(t/HMap :mandatory {:op ':if :test Expr :then Expr :else Expr} :complete? true)
(t/HMap :mandatory {:op ':case :selector Expr :arms Exprs} :complete? true)
(t/HMap :mandatory {:op ':dispatch :value Expr :spec CaseSpec} :complete? true)
(t/HMap :mandatory {:op ':throw :value Expr} :complete? true)
(t/HMap :mandatory {:op ':label :name t/Sym} :complete? true)
(t/HMap :mandatory {:op ':goto :name t/Sym} :complete? true)
(t/HMap :mandatory {:op ':do :forms (t/Vec Expr)} :complete? true)
(t/HMap :mandatory {:op ':let :bindings (t/Vec Binding) :body Expr} :complete? true)
(t/HMap :mandatory {:op ':loop :id t/Sym :bindings (t/Vec Binding) :body Expr} :complete? true)
(t/HMap :mandatory {:op ':recur :target RecurTarget :args (t/Vec Expr)} :complete? true))
Supply (t/HMap :mandatory {:prefix t/Str :next t/Int} :complete? true)
Compilation (t/HVec [Supply Expr])
Context (t/HMap :mandatory {:locals (t/Map t/Sym Local) :macro-env (t/Map t/Sym Raw)
:markers (t/Map t/AnyVar t/Kw) :outer? t/Bool :transfer? t/Bool
:site Site
:recur (t/Option RecurTarget) :statement? t/Bool :tail? t/Bool} :complete? true)})
(np/derive-language Native Bound
{:remove {Node #{:setq :psetq :label :goto}}})
(np/derive-language Classified Bound
{:add {Node [(t/HMap :mandatory {:op ':native :value l/Native-Expr}
:complete? true)]}})
(np/derive-language Assigned Classified
{:remove {Node #{:setq :psetq}}
:add {Node [(t/HMap :mandatory {:op ':write :target Local :value Expr} :complete? true)]}})
(np/derive-language Collections Assigned
{:remove {Node #{:collection}}
:add {Node [(t/HMap :mandatory {:op ':build :kind CollectionKind :items Exprs :unique? t/Bool
:metadata (t/Option Expr)} :complete? true)]}})
(np/derive-language Prepared Collections
{:remove {Node #{:host}}
:add {Node [(t/HMap :mandatory {:op ':host-call :operation l/JVM-Operation :args (t/Vec Expr)} :complete? true)
(t/HMap :mandatory {:op ':convert :conversion l/JVM-Conversion :value Expr} :complete? true)]}})
(np/derive-language Ordered Prepared
{:remove {Node #{:invoke :build :host-call :convert :recur :dispatch}}
:add {Node [(t/HMap :mandatory {:op ':convert :conversion l/JVM-Conversion :value Local} :complete? true)
(t/HMap :mandatory {:op ':dispatch :value Local :spec CaseSpec} :complete? true)
(t/HMap :mandatory {:op ':recur :target RecurTarget :args (t/Vec Local)} :complete? true)
(t/HMap :mandatory {:op ':host-call :operation l/JVM-Operation :args (t/Vec Local)} :complete? true)
(t/HMap :mandatory {:op ':invoke :function Local :args (t/Vec Local)} :complete? true)
(t/HMap :mandatory {:op ':build :kind CollectionKind :items (t/Vec Local) :unique? t/Bool} :complete? true)
(t/HMap :mandatory {:op ':metadata :value Local :metadata Local} :complete? true)]}})
;; Graph execution order is Symbolic -> CFG -> Machine. Derivation runs
;; the other way because earlier graphs extend the allocated machine grammar.
(np/deflanguage Machine
{Atom (t/U (t/HMap :mandatory {:op ':literal :value t/Any} :complete? true)
(t/HMap :mandatory {:op ':local :id t/Sym} :complete? true))
Operand (t/HMap :mandatory {:value Atom :jvm l/JVM-Fact} :complete? true)
Rhs (t/U (t/HMap :mandatory {:op ':convert :conversion l/JVM-Conversion :value Operand} :complete? true)
(t/HMap :mandatory {:op ':dispatch :value Operand :spec l/Bound-CaseSpec} :complete? true)
(t/HMap :mandatory {:op ':native :value l/Native-Expr} :complete? true)
(t/HMap :mandatory {:op ':host :operation l/JVM-Operation :args (t/Vec Operand)} :complete? true)
(t/HMap :mandatory {:op ':value :value Atom} :complete? true)
(t/HMap :mandatory {:op ':global :name t/Sym} :complete? true)
(t/HMap :mandatory {:op ':external :name t/Sym :jvm l/JVM-Fact} :complete? true)
(t/HMap :mandatory {:op ':var :name t/Sym} :complete? true)
(t/HMap :mandatory {:op ':construct :kind l/Bound-CollectionKind :items (t/Vec Atom) :unique? t/Bool} :complete? true)
(t/HMap :mandatory {:op ':metadata :value Atom :metadata Atom} :complete? true)
(t/HMap :mandatory {:op ':invoke :function Atom :args (t/Vec Atom)} :complete? true))
Operation (t/HMap :mandatory {:target t/Sym :value Rhs} :complete? true)
Term (t/U (t/HMap :mandatory {:op ':jump :target Label} :complete? true)
(t/HMap :mandatory {:op ':switch :test Atom :targets (t/Vec Label)} :complete? true)
(t/HMap :mandatory {:op ':branch :test Atom :yes Label :no Label} :complete? true)
(t/HMap :mandatory {:op ':return :value Atom} :complete? true)
(t/HMap :mandatory {:op ':throw :value Atom} :complete? true))
Block (t/HMap :mandatory {:ops (t/Vec Operation) :term Term} :complete? true)
Program (t/HMap :mandatory {:entry Label :slots (t/Vec t/Sym)
:blocks (t/Map Label Block) :live (t/Map Label (t/Set t/Sym))} :complete? true)
Label t/Int
Name t/Sym
Code (t/U t/Sym (t/Seq t/Any) (t/Vec t/Any))})
(np/derive-language CFG Machine
{:replace
{Program (t/HMap :mandatory {:entry Label :blocks (t/Map Label Block)} :complete? true)
BlockFacts (t/HMap :mandatory {:reads (t/Set t/Sym) :defs (t/Set t/Sym)
:successors (t/Vec Label)} :complete? true)
Facts (t/Map Label BlockFacts)
Labels (t/Set Label)
Flow (t/Map Label (t/Set t/Sym))
Predecessors (t/Map Label Labels)}})
(np/derive-language Symbolic CFG
{:add {Term [(t/HMap :mandatory {:op ':transfer :name t/Sym :site l/Bound-Site} :complete? true)]}
:replace
{LabelTable (t/Map t/Sym Label)
Program (t/HMap :mandatory {:entry Label :blocks (t/Map Label Block) :labels LabelTable} :complete? true)
Builder (t/HMap :mandatory {:supply l/Bound-Supply :ops (t/Vec Operation) :next Label :current Label
:blocks (t/Map Label Block) :labels LabelTable
:loops (t/Map t/Sym Label)} :complete? true)}})
;; Recognized numeric calls retain the original host operation and operands.
;; Value facts precede representation selection; neither changes source JVM facts.
;; A plan's origins index the operands whose references it may return unchanged.
(np/derive-language Numeric Machine
{:add {Rhs [(t/HMap :mandatory {:op ':numeric :args (t/Vec Operand)
:parameters (t/Vec java.lang.Class) :return java.lang.Class
:operation (t/HMap :mandatory {:op ':static :class java.lang.Class
:member t/Sym :tags l/JVM-Tags} :complete? true)}
:optional {:conversion l/JVM-Conversion} :complete? true)]}
:replace {ValueType (t/U ':bottom ':boxed java.lang.Class)
ArgumentTypes (t/Vec ValueType)
Plan (t/HMap :mandatory {:recipe (t/U ':call ':negate-add ':promoting-negate-add ':divide
':zero-guard ':select ':compare ':narrow-int ':narrow-char ':narrow-checked ':widen-char)
:parameters (t/Vec java.lang.Class) :result java.lang.Class
:origins (t/Vec t/Int)} :complete? true)
Blocks (t/Map Label Block)}})
;; Numeric value facts and control plans are independent backend analyses.
(np/deflanguage Analysis
{Type (t/U ':bottom ':boxed java.lang.Class)
Types (t/Map t/Sym Type)
Definitions (t/Map t/Sym (t/Vec l/Numeric-Rhs))
Program (t/HMap :mandatory {:machine l/Numeric-Program :types Types
:reachable (t/Set l/Machine-Label)} :complete? true)})
(np/deflanguage Planned
{Postdominators (t/Map l/Machine-Label (t/Set l/Machine-Label))
LoopBodies (t/Map l/Machine-Label (t/Set l/Machine-Label))
Region (t/HMap :mandatory {:blocks (t/Set l/Machine-Label) :changed (t/Set t/Sym)} :complete? true)
Regions (t/Map l/Machine-Label Region)
Join (t/HMap :mandatory {:target l/Machine-Label :results (t/Vec t/Sym)
:blocks (t/Set l/Machine-Label)} :complete? true)
Joins (t/Map l/Machine-Label Join)
Program (t/HMap :mandatory {:machine l/Numeric-Program :joins Joins
:loops (t/Option LoopBodies) :exits Joins} :complete? true)})
;; Structured recovery produces Joined expressions. Representation selection
;; produces Represented; lexical and numeric lowering follow it.
;; Returns carry one public result or the zero/many values of a lexical join.
(np/deflanguage Joined
{Expr (t/U (t/HMap :mandatory {:op ':bind :binding l/Numeric-Operation :body Expr} :complete? true)
(t/HMap :mandatory {:op ':branch :test l/Machine-Atom :yes Expr :no Expr} :complete? true)
(t/HMap :mandatory {:op ':switch :test l/Machine-Atom :arms (t/Vec Expr)} :complete? true)
(t/HMap :mandatory {:op ':loop :slots (t/Vec t/Sym) :body Expr} :complete? true)
(t/HMap :mandatory {:op ':recur :slots (t/Vec t/Sym)} :complete? true)
(t/HMap :mandatory {:op ':return :values (t/Vec l/Machine-Atom)} :complete? true)
(t/HMap :mandatory {:op ':throw :value l/Machine-Atom} :complete? true)
(t/HMap :mandatory {:op ':join :targets (t/Vec t/Sym) :value Expr :body Expr} :complete? true))
Build (t/U (t/HMap :mandatory {:op ':built :budget t/Int :expr Expr} :complete? true)
(t/HMap :mandatory {:op ':exhausted :reason Fallback} :complete? true))
Arms (t/U (t/HMap :mandatory {:op ':built :budget t/Int :arms (t/Vec Expr)} :complete? true)
(t/HMap :mandatory {:op ':exhausted :reason Fallback} :complete? true))
Fallback (t/U ':cycles ':validation ':budget)
Decision (t/U (t/HMap :mandatory {:op ':structured :body Expr} :complete? true)
(t/HMap :mandatory {:op ':fallback :reason Fallback} :complete? true))
Context (t/HMap :mandatory {:machine l/Numeric-Program :header (t/Option l/Machine-Label)
:slots (t/Vec t/Sym) :joins l/Planned-Joins
:loops l/Planned-LoopBodies :exits l/Planned-Joins
:active (t/Set l/Machine-Label)
:stop (t/Option (t/HVec [l/Machine-Label (t/Vec t/Sym)]))} :complete? true)})
(np/derive-language Represented Joined
{:replace {Types (t/Map t/Sym java.lang.Class)
Program (t/HMap :mandatory {:body Expr :types Types} :complete? true)}})
;; Lexical makes loop arguments and nested operands explicit before numeric
;; lowering. Compact removes numeric operations; simplification follows lowering.
(np/derive-language Lexical Numeric
{:replace
{Binding (t/HMap :mandatory {:target t/Sym :value Atom} :complete? true)
Expr (t/U (t/HMap :mandatory {:op ':bind :binding Operation :body Expr} :complete? true)
(t/HMap :mandatory {:op ':join :targets (t/Vec t/Sym) :value Expr :body Expr} :complete? true)
(t/HMap :mandatory {:op ':branch :test Atom :yes Expr :no Expr} :complete? true)
(t/HMap :mandatory {:op ':switch :test Atom :arms (t/Vec Expr)} :complete? true)
(t/HMap :mandatory {:op ':loop :bindings (t/Vec Binding) :body Expr} :complete? true)
(t/HMap :mandatory {:op ':recur :args (t/Vec Atom)} :complete? true)
(t/HMap :mandatory {:op ':return :values (t/Vec Atom)} :complete? true)
(t/HMap :mandatory {:op ':throw :value Atom} :complete? true))
Types (t/Map t/Sym java.lang.Class)
Program (t/HMap :mandatory {:body Expr :types Types} :complete? true)}})
(np/derive-language Compact Lexical
{:remove {Rhs #{:numeric}}
:add {Atom [(t/HMap :mandatory {:op ':inline :value Rhs :type (t/Option java.lang.Class)} :complete? true)]
Expr [(t/HMap :mandatory {:op ':effect :binding Operation :body Expr} :complete? true)]}})