@guildofweavers/air-assembly - npm Package Compare versions

Comparing version 0.2.1 to 0.2.2

air-assembly.d.ts

@@ -364,7 +364,11 @@ declare module '@guildofweavers/air-assembly' {
     export interface ProcedureAnalysisResult {
-        readonly degree     : bigint[];
+        readonly results: {
+            readonly degree     : bigint;
+            readonly traceRefs  : number[];
+            readonly staticRefs : number[];
+        }[];
         readonly operations : {
-            readonly add    : number;
-            readonly mul    : number;
-            readonly inv    : number;
+            readonly add        : number;
+            readonly mul        : number;
+            readonly inv        : number;
         };
@@ -462,2 +466,4 @@ }
         readonly degree     : number;
+        readonly traceRefs  : number[];
+        readonly staticRefs : number[];
     }
@@ -464,0 +470,0 @@

lib/AirComponent.js

@@ -122,4 +122,6 @@ "use strict";
             const constraintAnalysis = analysis_1.analyzeProcedure(this.constraintEvaluator);
-            this._constraints = constraintAnalysis.degree.map(d => ({
-                degree: d > Number.MAX_SAFE_INTEGER ? Number.MAX_SAFE_INTEGER : Number(d)
+            this._constraints = constraintAnalysis.results.map(r => ({
+                degree: r.degree > Number.MAX_SAFE_INTEGER ? Number.MAX_SAFE_INTEGER : Number(r.degree),
+                traceRefs: r.traceRefs,
+                staticRefs: r.staticRefs
             }));
@@ -126,0 +128,0 @@ }

lib/analysis/analyzer.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
 const expressions_1 = require("../expressions");
-const degree_1 = require("./degree");
 const operations_1 = require("./operations");
+const utils_1 = require("./utils");
 // EXPRESSION ANALYZER CLASS
@@ -12,3 +12,3 @@ // ================================================================================================
     literalValue(e) {
-        return dimensionsToDegree(e.dimensions, 0n);
+        return dimensionsToInfo(e.dimensions, 0n);
     }
@@ -18,13 +18,44 @@ // OPERATIONS
     binaryOperation(e, ctx) {
-        operations_1.analyzeBinaryOperation(e, ctx.stats);
-        const lhsDegree = this.visit(e.lhs, ctx);
-        const rhsDegree = this.visit(e.rhs, ctx);
-        const degree = degree_1.getBinaryOperationDegree(e, lhsDegree, rhsDegree);
-        return degree;
+        const lhsInfo = this.visit(e.lhs, ctx);
+        const rhsInfo = this.visit(e.rhs, ctx);
+        switch (e.operation) {
+            case 'add':
+            case 'sub': {
+                ctx.stats.add += operations_1.getSimpleOperationCount(e.lhs);
+                return operations_1.applySimpleOperation(operations_1.maxDegree, lhsInfo, rhsInfo);
+            }
+            case 'mul': {
+                ctx.stats.mul += operations_1.getSimpleOperationCount(e.lhs);
+                return operations_1.applySimpleOperation(operations_1.sumDegree, lhsInfo, rhsInfo);
+            }
+            case 'div': {
+                ctx.stats.mul += operations_1.getSimpleOperationCount(e.lhs);
+                ctx.stats.inv += 1;
+                return operations_1.applySimpleOperation(operations_1.sumDegree, lhsInfo, rhsInfo); // TODO: incorrect degree
+            }
+            case 'exp': {
+                const exponent = utils_1.getExponentValue(e.rhs);
+                ctx.stats.mul += operations_1.getExponentOperationCount(e.lhs, exponent);
+                return operations_1.applyExponentOperation(lhsInfo, exponent);
+            }
+            case 'prod': {
+                const counts = operations_1.getProductOperationCounts(e.lhs, e.rhs);
+                ctx.stats.mul += counts.mul;
+                ctx.stats.add += counts.add;
+                return operations_1.applyProductOperation(lhsInfo, rhsInfo);
+            }
+        }
     }
     unaryOperation(e, ctx) {
-        operations_1.analyzeUnaryOperation(e, ctx.stats);
-        const opDegree = this.visit(e, ctx);
-        const degree = degree_1.getUnaryOperationDegree(e, opDegree);
-        return degree;
+        const operandInfo = this.visit(e.operand, ctx);
+        switch (e.operation) {
+            case 'neg': {
+                ctx.stats.add += operations_1.getSimpleOperationCount(e.operand);
+                return operandInfo;
+            }
+            case 'inv': {
+                ctx.stats.inv += operations_1.getSimpleOperationCount(e.operand);
+                return operandInfo; // TODO: incorrect degree
+            }
+        }
     }
@@ -34,35 +65,38 @@ // VECTORS AND MATRIXES
     makeVector(e, ctx) {
-        let degree = [];
+        let result = [];
         for (let element of e.elements) {
-            const elementDegree = this.visit(element, ctx);
+            const elementInfo = this.visit(element, ctx);
             if (element.isScalar) {
-                degree.push(elementDegree);
+                result.push(elementInfo);
             }
             else if (element.isVector) {
-                degree = degree.concat(elementDegree);
+                result = result.concat(elementInfo);
             }
         }
-        return degree;
+        return result;
     }
     getVectorElement(e, ctx) {
-        const sourceDegree = this.visit(e.source, ctx);
-        return sourceDegree[e.index];
+        const sourceItems = this.visit(e.source, ctx);
+        return sourceItems[e.index];
     }
     sliceVector(e, ctx) {
-        const sourceDegree = this.visit(e.source, ctx);
-        return sourceDegree.slice(e.start, e.end + 1);
+        const sourceItems = this.visit(e.source, ctx);
+        return sourceItems.slice(e.start, e.end + 1);
     }
     makeMatrix(e, ctx) {
-        const degree = [];
+        const result = [];
         for (let row of e.elements) {
-            let rowDegree = [];
+            let rowInfo = [];
             for (let element of row) {
-                const elementDegree = this.visit(element, ctx);
+                const elementInfo = this.visit(element, ctx);
                 if (element.isScalar) {
-                    rowDegree.push(elementDegree);
+                    rowInfo.push(elementInfo);
                 }
+                else if (element.isVector) {
+                    rowInfo = rowInfo.concat(elementInfo);
+                }
             }
-            degree.push(rowDegree);
+            result.push(rowInfo);
         }
-        return degree;
+        return result;
     }
@@ -72,12 +106,9 @@ // LOAD AND STORE
     loadExpression(e, ctx) {
-        if (e.source === 'const')
-            return ctx.degree.const[e.index];
-        else if (e.source === 'param')
-            return ctx.degree.param[e.index];
-        else if (e.source === 'local')
-            return ctx.degree.local[e.index];
-        else if (e.source === 'static')
-            return ctx.degree.static;
-        else
-            return ctx.degree.trace;
+        switch (e.source) {
+            case 'const': return ctx.info.const[e.index];
+            case 'param': return ctx.info.param[e.index];
+            case 'local': return ctx.info.local[e.index];
+            case 'trace': return dimensionsToInfo(ctx.info.trace, 1n, new Set([e.index]), new Set());
+            case 'static': return dimensionsToInfo(ctx.info.static, 1n, new Set(), new Set([e.index]));
+        }
     }
@@ -88,3 +119,3 @@ // CALL EXPRESSION
         const fnContext = {
-            degree: { ...ctx.degree, param: [], local: [] },
+            info: { ...ctx.info, param: [], local: [] },
             stats: ctx.stats
@@ -94,9 +125,7 @@ };
         e.params.forEach((p, i) => {
-            const degree = this.visit(p, fnContext);
-            fnContext.degree.param[i] = degree;
+            fnContext.info.param[i] = this.visit(p, fnContext);
         });
         // analyze statements
         e.func.statements.forEach(s => {
-            const degree = this.visit(s.expression, fnContext);
-            fnContext.degree.local[s.target] = degree;
+            fnContext.info.local[s.target] = this.visit(s.expression, fnContext);
         });
@@ -112,8 +141,8 @@ return this.visit(e.func.result, fnContext);
     const context = {
-        degree: {
-            const: procedure.constants.map(c => dimensionsToDegree(c.dimensions, 0n)),
+        info: {
+            const: procedure.constants.map(c => dimensionsToInfo(c.dimensions)),
             param: [],
             local: new Array(procedure.locals.length),
-            static: dimensionsToDegree(procedure.staticRegisters.dimensions, 1n),
-            trace: dimensionsToDegree(procedure.traceRegisters.dimensions, 1n)
+            static: procedure.staticRegisters.dimensions,
+            trace: procedure.traceRegisters.dimensions
         },
@@ -124,8 +153,12 @@ stats: { add: 0, mul: 0, inv: 0 }
     procedure.statements.forEach(s => {
-        const degree = analyzer.visit(s.expression, context);
-        context.degree.local[s.target] = degree;
+        context.info.local[s.target] = analyzer.visit(s.expression, context);
     });
     // analyze result and return
-    const degree = analyzer.visit(procedure.result, context);
-    return { degree, operations: context.stats };
+    const procedureInfo = analyzer.visit(procedure.result, context);
+    const results = procedureInfo.map(item => ({
+        degree: item.degree,
+        traceRefs: Array.from(item.traceRefs).sort((a, b) => a - b),
+        staticRefs: Array.from(item.staticRefs).sort((a, b) => a - b)
+    }));
+    return { results, operations: context.stats };
 }
@@ -135,13 +168,13 @@ exports.analyzeProcedure = analyzeProcedure;
 // ================================================================================================
-function dimensionsToDegree(dimensions, degree) {
+function dimensionsToInfo(dimensions, degree = 0n, traceRefs = new Set(), staticRefs = new Set()) {
     if (expressions_1.Dimensions.isScalar(dimensions)) {
-        return degree;
+        return { degree, staticRefs, traceRefs };
     }
     else if (expressions_1.Dimensions.isVector(dimensions)) {
-        return new Array(dimensions[0]).fill(degree);
+        return new Array(dimensions[0]).fill({ degree, staticRefs, traceRefs });
     }
     else {
-        return new Array(dimensions[0]).fill(new Array(dimensions[1]).fill(degree));
+        return new Array(dimensions[0]).fill(new Array(dimensions[1]).fill({ degree, staticRefs, traceRefs }));
     }
 }
 //# sourceMappingURL=analyzer.js.map

lib/analysis/operations.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-const utils_1 = require("./utils");
-// PUBLIC FUNCTIONS
+// OPERATION COUNT FUNCTIONS
 // ================================================================================================
-function analyzeBinaryOperation(e, stats) {
-    switch (e.operation) {
-        case 'add':
-        case 'sub': {
-            stats.add += getSimpleOperationCount(e.lhs);
-            break;
+function getSimpleOperationCount(e) {
+    if (e.isScalar)
+        return 1;
+    else if (e.isVector)
+        return e.dimensions[0];
+    else
+        return e.dimensions[0] * e.dimensions[1];
+}
+exports.getSimpleOperationCount = getSimpleOperationCount;
+function getExponentOperationCount(base, exponent) {
+    const opCount = getSimpleOperationCount(base);
+    let mulCount = 0;
+    while (exponent) {
+        exponent = exponent >> 1n;
+        mulCount++;
+    }
+    return opCount * mulCount;
+}
+exports.getExponentOperationCount = getExponentOperationCount;
+function getProductOperationCounts(lhs, rhs) {
+    let add = 0, mul = 0;
+    if (lhs.isVector) {
+        mul += lhs.dimensions[0];
+        add += lhs.dimensions[0] - 1;
+    }
+    else if (lhs.isMatrix && rhs.isVector) {
+        mul += lhs.dimensions[0] * lhs.dimensions[1];
+        add += rhs.dimensions[0] * (lhs.dimensions[1] - 1);
+    }
+    else {
+        mul += lhs.dimensions[0] * lhs.dimensions[1] * rhs.dimensions[1];
+        add += rhs.dimensions[0] * (lhs.dimensions[1] - 1) * rhs.dimensions[1];
+    }
+    return { add, mul };
+}
+exports.getProductOperationCounts = getProductOperationCounts;
+// OPERATION APPLICATION FUNCTIONS
+// ================================================================================================
+function applySimpleOperation(degreeOp, lhs, rhs) {
+    if (isScalar(lhs)) {
+        const v2 = rhs;
+        return {
+            degree: degreeOp(lhs.degree, v2.degree),
+            traceRefs: mergeReferences(lhs.traceRefs, v2.traceRefs),
+            staticRefs: mergeReferences(lhs.staticRefs, v2.staticRefs)
+        };
+    }
+    else if (isVector(lhs)) {
+        return applyToVector(degreeOp, lhs, rhs);
+    }
+    else {
+        return applyToMatrix(degreeOp, lhs, rhs);
+    }
+}
+exports.applySimpleOperation = applySimpleOperation;
+function applyExponentOperation(base, exponent) {
+    if (isScalar(base)) {
+        return mulDegree(base, exponent);
+    }
+    else if (isVector(base)) {
+        return base.map(item => mulDegree(item, exponent));
+    }
+    else {
+        return base.map(row => row.map(item => mulDegree(item, exponent)));
+    }
+}
+exports.applyExponentOperation = applyExponentOperation;
+function applyProductOperation(lhs, rhs) {
+    if (isVector(lhs) && isVector(rhs)) {
+        return applyLinearCombination(lhs, rhs);
+    }
+    else if (isMatrix(lhs) && isVector(rhs)) {
+        return applyMatrixVectorProduct(lhs, rhs);
+    }
+    else if (isMatrix(lhs) && isMatrix(rhs)) {
+        return applyMatrixMatrixProduct(lhs, rhs);
+    }
+    else {
+        throw new Error(`invalid product operation`);
+    }
+}
+exports.applyProductOperation = applyProductOperation;
+function maxDegree(d1, d2) {
+    return (d1 > d2) ? d1 : d2;
+}
+exports.maxDegree = maxDegree;
+function sumDegree(d1, d2) {
+    return d1 + d2;
+}
+exports.sumDegree = sumDegree;
+// HELPER FUNCTIONS
+// ================================================================================================
+function applyToVector(op, lhs, rhs) {
+    const result = new Array(lhs.length);
+    for (let i = 0; i < lhs.length; i++) {
+        let v1 = lhs[i];
+        let v2 = (Array.isArray(rhs) ? rhs[i] : rhs);
+        result[i] = {
+            degree: op(v1.degree, v2.degree),
+            traceRefs: mergeReferences(v1.traceRefs, v2.traceRefs),
+            staticRefs: mergeReferences(v1.staticRefs, v2.staticRefs)
+        };
+    }
+    return result;
+}
+function applyToMatrix(op, lhs, rhs) {
+    const result = new Array(lhs.length);
+    for (let i = 0; i < lhs.length; i++) {
+        result[i] = new Array(lhs[i].length);
+        for (let j = 0; j < lhs[i].length; j++) {
+            let v1 = lhs[i][j];
+            let v2 = (Array.isArray(rhs) ? rhs[i][j] : rhs);
+            result[i][j] = {
+                degree: op(v1.degree, v2.degree),
+                traceRefs: mergeReferences(v1.traceRefs, v2.traceRefs),
+                staticRefs: mergeReferences(v1.staticRefs, v2.staticRefs)
+            };
         }
-        case 'mul': {
-            stats.mul += getSimpleOperationCount(e.lhs);
-            break;
+    }
+    return result;
+}
+function mulDegree(base, exponent) {
+    return {
+        degree: base.degree * exponent,
+        traceRefs: base.traceRefs,
+        staticRefs: base.staticRefs
+    };
+}
+function applyLinearCombination(lhs, rhs) {
+    const traceRefs = new Set();
+    const staticRefs = new Set();
+    let degree = 0n;
+    for (let i = 0; i < lhs.length; i++) {
+        let v1 = lhs[i], v2 = rhs[i];
+        let d = v1.degree + v2.degree;
+        if (d > degree) {
+            degree = d;
         }
-        case 'div': {
-            stats.mul += getSimpleOperationCount(e.lhs);
-            stats.inv += 1;
-            break;
-        }
-        case 'exp': {
-            const opCount = getSimpleOperationCount(e.lhs);
-            let exponent = utils_1.getExponentValue(e.rhs);
-            let mulCount = 0;
-            while (exponent) {
-                exponent = exponent >> 1n;
-                mulCount++;
+        v1.traceRefs.forEach(r => traceRefs.add(r));
+        v2.traceRefs.forEach(r => traceRefs.add(r));
+        v1.staticRefs.forEach(r => staticRefs.add(r));
+        v2.staticRefs.forEach(r => staticRefs.add(r));
+    }
+    return { degree, traceRefs, staticRefs };
+}
+function applyMatrixVectorProduct(lhs, rhs) {
+    const result = new Array();
+    for (let row of lhs) {
+        result.push(applyLinearCombination(row, rhs));
+    }
+    return result;
+}
+function applyMatrixMatrixProduct(lhs, rhs) {
+    const n = lhs.length;
+    const m = lhs[0].length;
+    const p = rhs[0].length;
+    const result = new Array(n);
+    for (let i = 0; i < n; i++) {
+        let row = result[i] = new Array(p);
+        for (let j = 0; j < p; j++) {
+            let degree = 0n;
+            let traceRefs = new Set();
+            let staticRefs = new Set();
+            for (let k = 0; k < m; k++) {
+                let v1 = lhs[i][k], v2 = rhs[k][j];
+                let d = v1.degree + v2.degree;
+                if (d > degree) {
+                    degree = d;
+                }
+                ;
+                v1.traceRefs.forEach(r => traceRefs.add(r));
+                v2.traceRefs.forEach(r => traceRefs.add(r));
+                v1.staticRefs.forEach(r => staticRefs.add(r));
+                v2.staticRefs.forEach(r => staticRefs.add(r));
             }
-            stats.mul += opCount * mulCount;
-            break;
+            row[j] = { degree, traceRefs, staticRefs };
         }
-        case 'prod': {
-            if (e.lhs.isVector) {
-                stats.mul += e.lhs.dimensions[0];
-                stats.add += e.lhs.dimensions[0] - 1;
-            }
-            else if (e.lhs.isMatrix && e.rhs.isVector) {
-                stats.mul += e.lhs.dimensions[0] * e.lhs.dimensions[1];
-                stats.add += e.rhs.dimensions[0] * (e.lhs.dimensions[1] - 1);
-            }
-            else {
-                stats.mul += e.lhs.dimensions[0] * e.lhs.dimensions[1] * e.rhs.dimensions[1];
-                stats.add += e.rhs.dimensions[0] * (e.lhs.dimensions[1] - 1) * e.rhs.dimensions[1];
-            }
-            break;
-        }
     }
+    return result;
 }
-exports.analyzeBinaryOperation = analyzeBinaryOperation;
-function analyzeUnaryOperation(e, stats) {
-    switch (e.operation) {
-        case 'neg': {
-            stats.add += getSimpleOperationCount(e.operand);
-            break;
-        }
-        case 'inv': {
-            stats.inv += getSimpleOperationCount(e.operand);
-            break;
-        }
+function isScalar(info) {
+    return (!Array.isArray(info));
+}
+function isVector(info) {
+    return (Array.isArray(info) && !Array.isArray(info[0]));
+}
+function isMatrix(info) {
+    return (Array.isArray(info) && Array.isArray(info[0]));
+}
+function mergeReferences(r1, r2) {
+    const result = new Set(r1);
+    for (let r of r2) {
+        result.add(r);
     }
+    return result;
 }
-exports.analyzeUnaryOperation = analyzeUnaryOperation;
-// HELPER FUNCTIONS
-// ================================================================================================
-function getSimpleOperationCount(e) {
-    if (e.isScalar)
-        return 1;
-    else if (e.isVector)
-        return e.dimensions[0];
-    else
-        return e.dimensions[0] * e.dimensions[1];
-}
 //# sourceMappingURL=operations.js.map

package.json

 {
   "name": "@guildofweavers/air-assembly",
-  "version": "0.2.1",
+  "version": "0.2.2",
   "description": "A low-level language for encoding Algebraic Intermediate Representation of computations",
@@ -5,0 +5,0 @@ "main": "index.js",

No alert changes

Improved metrics

Total package byte prevSize

237754

increased by0.74%

Lines of code

4407

increased by0.59%

Worsened metrics

Number of package files

56

decreased by-1.75%

No dependency changes