Brunobkr/llama.cpp_AlgMor24_github

1/*2  Copyright (C) 2012-2013 Yusuke Suzuki <utatane.tea@gmail.com>3  Copyright (C) 2012 Ariya Hidayat <ariya.hidayat@gmail.com>4 5  Redistribution and use in source and binary forms, with or without6  modification, are permitted provided that the following conditions are met:7 8    * Redistributions of source code must retain the above copyright9      notice, this list of conditions and the following disclaimer.10    * Redistributions in binary form must reproduce the above copyright11      notice, this list of conditions and the following disclaimer in the12      documentation and/or other materials provided with the distribution.13 14  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"15  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE16  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE17  ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY18  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES19  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;20  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND21  ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT22  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF23  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.24*/25/*jslint vars:false, bitwise:true*/26/*jshint indent:4*/27/*global exports:true*/28(function clone(exports) {29    'use strict';30 31    var Syntax,32        VisitorOption,33        VisitorKeys,34        BREAK,35        SKIP,36        REMOVE;37 38    function deepCopy(obj) {39        var ret = {}, key, val;40        for (key in obj) {41            if (obj.hasOwnProperty(key)) {42                val = obj[key];43                if (typeof val === 'object' && val !== null) {44                    ret[key] = deepCopy(val);45                } else {46                    ret[key] = val;47                }48            }49        }50        return ret;51    }52 53    // based on LLVM libc++ upper_bound / lower_bound54    // MIT License55 56    function upperBound(array, func) {57        var diff, len, i, current;58 59        len = array.length;60        i = 0;61 62        while (len) {63            diff = len >>> 1;64            current = i + diff;65            if (func(array[current])) {66                len = diff;67            } else {68                i = current + 1;69                len -= diff + 1;70            }71        }72        return i;73    }74 75    Syntax = {76        AssignmentExpression: 'AssignmentExpression',77        AssignmentPattern: 'AssignmentPattern',78        ArrayExpression: 'ArrayExpression',79        ArrayPattern: 'ArrayPattern',80        ArrowFunctionExpression: 'ArrowFunctionExpression',81        AwaitExpression: 'AwaitExpression', // CAUTION: It's deferred to ES7.82        BlockStatement: 'BlockStatement',83        BinaryExpression: 'BinaryExpression',84        BreakStatement: 'BreakStatement',85        CallExpression: 'CallExpression',86        CatchClause: 'CatchClause',87        ChainExpression: 'ChainExpression',88        ClassBody: 'ClassBody',89        ClassDeclaration: 'ClassDeclaration',90        ClassExpression: 'ClassExpression',91        ComprehensionBlock: 'ComprehensionBlock',  // CAUTION: It's deferred to ES7.92        ComprehensionExpression: 'ComprehensionExpression',  // CAUTION: It's deferred to ES7.93        ConditionalExpression: 'ConditionalExpression',94        ContinueStatement: 'ContinueStatement',95        DebuggerStatement: 'DebuggerStatement',96        DirectiveStatement: 'DirectiveStatement',97        DoWhileStatement: 'DoWhileStatement',98        EmptyStatement: 'EmptyStatement',99        ExportAllDeclaration: 'ExportAllDeclaration',100        ExportDefaultDeclaration: 'ExportDefaultDeclaration',101        ExportNamedDeclaration: 'ExportNamedDeclaration',102        ExportSpecifier: 'ExportSpecifier',103        ExpressionStatement: 'ExpressionStatement',104        ForStatement: 'ForStatement',105        ForInStatement: 'ForInStatement',106        ForOfStatement: 'ForOfStatement',107        FunctionDeclaration: 'FunctionDeclaration',108        FunctionExpression: 'FunctionExpression',109        GeneratorExpression: 'GeneratorExpression',  // CAUTION: It's deferred to ES7.110        Identifier: 'Identifier',111        IfStatement: 'IfStatement',112        ImportExpression: 'ImportExpression',113        ImportDeclaration: 'ImportDeclaration',114        ImportDefaultSpecifier: 'ImportDefaultSpecifier',115        ImportNamespaceSpecifier: 'ImportNamespaceSpecifier',116        ImportSpecifier: 'ImportSpecifier',117        Literal: 'Literal',118        LabeledStatement: 'LabeledStatement',119        LogicalExpression: 'LogicalExpression',120        MemberExpression: 'MemberExpression',121        MetaProperty: 'MetaProperty',122        MethodDefinition: 'MethodDefinition',123        ModuleSpecifier: 'ModuleSpecifier',124        NewExpression: 'NewExpression',125        ObjectExpression: 'ObjectExpression',126        ObjectPattern: 'ObjectPattern',127        PrivateIdentifier: 'PrivateIdentifier',128        Program: 'Program',129        Property: 'Property',130        PropertyDefinition: 'PropertyDefinition',131        RestElement: 'RestElement',132        ReturnStatement: 'ReturnStatement',133        SequenceExpression: 'SequenceExpression',134        SpreadElement: 'SpreadElement',135        Super: 'Super',136        SwitchStatement: 'SwitchStatement',137        SwitchCase: 'SwitchCase',138        TaggedTemplateExpression: 'TaggedTemplateExpression',139        TemplateElement: 'TemplateElement',140        TemplateLiteral: 'TemplateLiteral',141        ThisExpression: 'ThisExpression',142        ThrowStatement: 'ThrowStatement',143        TryStatement: 'TryStatement',144        UnaryExpression: 'UnaryExpression',145        UpdateExpression: 'UpdateExpression',146        VariableDeclaration: 'VariableDeclaration',147        VariableDeclarator: 'VariableDeclarator',148        WhileStatement: 'WhileStatement',149        WithStatement: 'WithStatement',150        YieldExpression: 'YieldExpression'151    };152 153    VisitorKeys = {154        AssignmentExpression: ['left', 'right'],155        AssignmentPattern: ['left', 'right'],156        ArrayExpression: ['elements'],157        ArrayPattern: ['elements'],158        ArrowFunctionExpression: ['params', 'body'],159        AwaitExpression: ['argument'], // CAUTION: It's deferred to ES7.160        BlockStatement: ['body'],161        BinaryExpression: ['left', 'right'],162        BreakStatement: ['label'],163        CallExpression: ['callee', 'arguments'],164        CatchClause: ['param', 'body'],165        ChainExpression: ['expression'],166        ClassBody: ['body'],167        ClassDeclaration: ['id', 'superClass', 'body'],168        ClassExpression: ['id', 'superClass', 'body'],169        ComprehensionBlock: ['left', 'right'],  // CAUTION: It's deferred to ES7.170        ComprehensionExpression: ['blocks', 'filter', 'body'],  // CAUTION: It's deferred to ES7.171        ConditionalExpression: ['test', 'consequent', 'alternate'],172        ContinueStatement: ['label'],173        DebuggerStatement: [],174        DirectiveStatement: [],175        DoWhileStatement: ['body', 'test'],176        EmptyStatement: [],177        ExportAllDeclaration: ['source'],178        ExportDefaultDeclaration: ['declaration'],179        ExportNamedDeclaration: ['declaration', 'specifiers', 'source'],180        ExportSpecifier: ['exported', 'local'],181        ExpressionStatement: ['expression'],182        ForStatement: ['init', 'test', 'update', 'body'],183        ForInStatement: ['left', 'right', 'body'],184        ForOfStatement: ['left', 'right', 'body'],185        FunctionDeclaration: ['id', 'params', 'body'],186        FunctionExpression: ['id', 'params', 'body'],187        GeneratorExpression: ['blocks', 'filter', 'body'],  // CAUTION: It's deferred to ES7.188        Identifier: [],189        IfStatement: ['test', 'consequent', 'alternate'],190        ImportExpression: ['source'],191        ImportDeclaration: ['specifiers', 'source'],192        ImportDefaultSpecifier: ['local'],193        ImportNamespaceSpecifier: ['local'],194        ImportSpecifier: ['imported', 'local'],195        Literal: [],196        LabeledStatement: ['label', 'body'],197        LogicalExpression: ['left', 'right'],198        MemberExpression: ['object', 'property'],199        MetaProperty: ['meta', 'property'],200        MethodDefinition: ['key', 'value'],201        ModuleSpecifier: [],202        NewExpression: ['callee', 'arguments'],203        ObjectExpression: ['properties'],204        ObjectPattern: ['properties'],205        PrivateIdentifier: [],206        Program: ['body'],207        Property: ['key', 'value'],208        PropertyDefinition: ['key', 'value'],209        RestElement: [ 'argument' ],210        ReturnStatement: ['argument'],211        SequenceExpression: ['expressions'],212        SpreadElement: ['argument'],213        Super: [],214        SwitchStatement: ['discriminant', 'cases'],215        SwitchCase: ['test', 'consequent'],216        TaggedTemplateExpression: ['tag', 'quasi'],217        TemplateElement: [],218        TemplateLiteral: ['quasis', 'expressions'],219        ThisExpression: [],220        ThrowStatement: ['argument'],221        TryStatement: ['block', 'handler', 'finalizer'],222        UnaryExpression: ['argument'],223        UpdateExpression: ['argument'],224        VariableDeclaration: ['declarations'],225        VariableDeclarator: ['id', 'init'],226        WhileStatement: ['test', 'body'],227        WithStatement: ['object', 'body'],228        YieldExpression: ['argument']229    };230 231    // unique id232    BREAK = {};233    SKIP = {};234    REMOVE = {};235 236    VisitorOption = {237        Break: BREAK,238        Skip: SKIP,239        Remove: REMOVE240    };241 242    function Reference(parent, key) {243        this.parent = parent;244        this.key = key;245    }246 247    Reference.prototype.replace = function replace(node) {248        this.parent[this.key] = node;249    };250 251    Reference.prototype.remove = function remove() {252        if (Array.isArray(this.parent)) {253            this.parent.splice(this.key, 1);254            return true;255        } else {256            this.replace(null);257            return false;258        }259    };260 261    function Element(node, path, wrap, ref) {262        this.node = node;263        this.path = path;264        this.wrap = wrap;265        this.ref = ref;266    }267 268    function Controller() { }269 270    // API:271    // return property path array from root to current node272    Controller.prototype.path = function path() {273        var i, iz, j, jz, result, element;274 275        function addToPath(result, path) {276            if (Array.isArray(path)) {277                for (j = 0, jz = path.length; j < jz; ++j) {278                    result.push(path[j]);279                }280            } else {281                result.push(path);282            }283        }284 285        // root node286        if (!this.__current.path) {287            return null;288        }289 290        // first node is sentinel, second node is root element291        result = [];292        for (i = 2, iz = this.__leavelist.length; i < iz; ++i) {293            element = this.__leavelist[i];294            addToPath(result, element.path);295        }296        addToPath(result, this.__current.path);297        return result;298    };299 300    // API:301    // return type of current node302    Controller.prototype.type = function () {303        var node = this.current();304        return node.type || this.__current.wrap;305    };306 307    // API:308    // return array of parent elements309    Controller.prototype.parents = function parents() {310        var i, iz, result;311 312        // first node is sentinel313        result = [];314        for (i = 1, iz = this.__leavelist.length; i < iz; ++i) {315            result.push(this.__leavelist[i].node);316        }317 318        return result;319    };320 321    // API:322    // return current node323    Controller.prototype.current = function current() {324        return this.__current.node;325    };326 327    Controller.prototype.__execute = function __execute(callback, element) {328        var previous, result;329 330        result = undefined;331 332        previous  = this.__current;333        this.__current = element;334        this.__state = null;335        if (callback) {336            result = callback.call(this, element.node, this.__leavelist[this.__leavelist.length - 1].node);337        }338        this.__current = previous;339 340        return result;341    };342 343    // API:344    // notify control skip / break345    Controller.prototype.notify = function notify(flag) {346        this.__state = flag;347    };348 349    // API:350    // skip child nodes of current node351    Controller.prototype.skip = function () {352        this.notify(SKIP);353    };354 355    // API:356    // break traversals357    Controller.prototype['break'] = function () {358        this.notify(BREAK);359    };360 361    // API:362    // remove node363    Controller.prototype.remove = function () {364        this.notify(REMOVE);365    };366 367    Controller.prototype.__initialize = function(root, visitor) {368        this.visitor = visitor;369        this.root = root;370        this.__worklist = [];371        this.__leavelist = [];372        this.__current = null;373        this.__state = null;374        this.__fallback = null;375        if (visitor.fallback === 'iteration') {376            this.__fallback = Object.keys;377        } else if (typeof visitor.fallback === 'function') {378            this.__fallback = visitor.fallback;379        }380 381        this.__keys = VisitorKeys;382        if (visitor.keys) {383            this.__keys = Object.assign(Object.create(this.__keys), visitor.keys);384        }385    };386 387    function isNode(node) {388        if (node == null) {389            return false;390        }391        return typeof node === 'object' && typeof node.type === 'string';392    }393 394    function isProperty(nodeType, key) {395        return (nodeType === Syntax.ObjectExpression || nodeType === Syntax.ObjectPattern) && 'properties' === key;396    }397  398    function candidateExistsInLeaveList(leavelist, candidate) {399        for (var i = leavelist.length - 1; i >= 0; --i) {400            if (leavelist[i].node === candidate) {401                return true;402            }403        }404        return false;405    }406 407    Controller.prototype.traverse = function traverse(root, visitor) {408        var worklist,409            leavelist,410            element,411            node,412            nodeType,413            ret,414            key,415            current,416            current2,417            candidates,418            candidate,419            sentinel;420 421        this.__initialize(root, visitor);422 423        sentinel = {};424 425        // reference426        worklist = this.__worklist;427        leavelist = this.__leavelist;428 429        // initialize430        worklist.push(new Element(root, null, null, null));431        leavelist.push(new Element(null, null, null, null));432 433        while (worklist.length) {434            element = worklist.pop();435 436            if (element === sentinel) {437                element = leavelist.pop();438 439                ret = this.__execute(visitor.leave, element);440 441                if (this.__state === BREAK || ret === BREAK) {442                    return;443                }444                continue;445            }446 447            if (element.node) {448 449                ret = this.__execute(visitor.enter, element);450 451                if (this.__state === BREAK || ret === BREAK) {452                    return;453                }454 455                worklist.push(sentinel);456                leavelist.push(element);457 458                if (this.__state === SKIP || ret === SKIP) {459                    continue;460                }461 462                node = element.node;463                nodeType = node.type || element.wrap;464                candidates = this.__keys[nodeType];465                if (!candidates) {466                    if (this.__fallback) {467                        candidates = this.__fallback(node);468                    } else {469                        throw new Error('Unknown node type ' + nodeType + '.');470                    }471                }472 473                current = candidates.length;474                while ((current -= 1) >= 0) {475                    key = candidates[current];476                    candidate = node[key];477                    if (!candidate) {478                        continue;479                    }480 481                    if (Array.isArray(candidate)) {482                        current2 = candidate.length;483                        while ((current2 -= 1) >= 0) {484                            if (!candidate[current2]) {485                                continue;486                            }487 488                            if (candidateExistsInLeaveList(leavelist, candidate[current2])) {489                              continue;490                            }491 492                            if (isProperty(nodeType, candidates[current])) {493                                element = new Element(candidate[current2], [key, current2], 'Property', null);494                            } else if (isNode(candidate[current2])) {495                                element = new Element(candidate[current2], [key, current2], null, null);496                            } else {497                                continue;498                            }499                            worklist.push(element);500                        }501                    } else if (isNode(candidate)) {502                        if (candidateExistsInLeaveList(leavelist, candidate)) {503                          continue;504                        }505 506                        worklist.push(new Element(candidate, key, null, null));507                    }508                }509            }510        }511    };512 513    Controller.prototype.replace = function replace(root, visitor) {514        var worklist,515            leavelist,516            node,517            nodeType,518            target,519            element,520            current,521            current2,522            candidates,523            candidate,524            sentinel,525            outer,526            key;527 528        function removeElem(element) {529            var i,530                key,531                nextElem,532                parent;533 534            if (element.ref.remove()) {535                // When the reference is an element of an array.536                key = element.ref.key;537                parent = element.ref.parent;538 539                // If removed from array, then decrease following items' keys.540                i = worklist.length;541                while (i--) {542                    nextElem = worklist[i];543                    if (nextElem.ref && nextElem.ref.parent === parent) {544                        if  (nextElem.ref.key < key) {545                            break;546                        }547                        --nextElem.ref.key;548                    }549                }550            }551        }552 553        this.__initialize(root, visitor);554 555        sentinel = {};556 557        // reference558        worklist = this.__worklist;559        leavelist = this.__leavelist;560 561        // initialize562        outer = {563            root: root564        };565        element = new Element(root, null, null, new Reference(outer, 'root'));566        worklist.push(element);567        leavelist.push(element);568 569        while (worklist.length) {570            element = worklist.pop();571 572            if (element === sentinel) {573                element = leavelist.pop();574 575                target = this.__execute(visitor.leave, element);576 577                // node may be replaced with null,578                // so distinguish between undefined and null in this place579                if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {580                    // replace581                    element.ref.replace(target);582                }583 584                if (this.__state === REMOVE || target === REMOVE) {585                    removeElem(element);586                }587 588                if (this.__state === BREAK || target === BREAK) {589                    return outer.root;590                }591                continue;592            }593 594            target = this.__execute(visitor.enter, element);595 596            // node may be replaced with null,597            // so distinguish between undefined and null in this place598            if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {599                // replace600                element.ref.replace(target);601                element.node = target;602            }603 604            if (this.__state === REMOVE || target === REMOVE) {605                removeElem(element);606                element.node = null;607            }608 609            if (this.__state === BREAK || target === BREAK) {610                return outer.root;611            }612 613            // node may be null614            node = element.node;615            if (!node) {616                continue;617            }618 619            worklist.push(sentinel);620            leavelist.push(element);621 622            if (this.__state === SKIP || target === SKIP) {623                continue;624            }625 626            nodeType = node.type || element.wrap;627            candidates = this.__keys[nodeType];628            if (!candidates) {629                if (this.__fallback) {630                    candidates = this.__fallback(node);631                } else {632                    throw new Error('Unknown node type ' + nodeType + '.');633                }634            }635 636            current = candidates.length;637            while ((current -= 1) >= 0) {638                key = candidates[current];639                candidate = node[key];640                if (!candidate) {641                    continue;642                }643 644                if (Array.isArray(candidate)) {645                    current2 = candidate.length;646                    while ((current2 -= 1) >= 0) {647                        if (!candidate[current2]) {648                            continue;649                        }650                        if (isProperty(nodeType, candidates[current])) {651                            element = new Element(candidate[current2], [key, current2], 'Property', new Reference(candidate, current2));652                        } else if (isNode(candidate[current2])) {653                            element = new Element(candidate[current2], [key, current2], null, new Reference(candidate, current2));654                        } else {655                            continue;656                        }657                        worklist.push(element);658                    }659                } else if (isNode(candidate)) {660                    worklist.push(new Element(candidate, key, null, new Reference(node, key)));661                }662            }663        }664 665        return outer.root;666    };667 668    function traverse(root, visitor) {669        var controller = new Controller();670        return controller.traverse(root, visitor);671    }672 673    function replace(root, visitor) {674        var controller = new Controller();675        return controller.replace(root, visitor);676    }677 678    function extendCommentRange(comment, tokens) {679        var target;680 681        target = upperBound(tokens, function search(token) {682            return token.range[0] > comment.range[0];683        });684 685        comment.extendedRange = [comment.range[0], comment.range[1]];686 687        if (target !== tokens.length) {688            comment.extendedRange[1] = tokens[target].range[0];689        }690 691        target -= 1;692        if (target >= 0) {693            comment.extendedRange[0] = tokens[target].range[1];694        }695 696        return comment;697    }698 699    function attachComments(tree, providedComments, tokens) {700        // At first, we should calculate extended comment ranges.701        var comments = [], comment, len, i, cursor;702 703        if (!tree.range) {704            throw new Error('attachComments needs range information');705        }706 707        // tokens array is empty, we attach comments to tree as 'leadingComments'708        if (!tokens.length) {709            if (providedComments.length) {710                for (i = 0, len = providedComments.length; i < len; i += 1) {711                    comment = deepCopy(providedComments[i]);712                    comment.extendedRange = [0, tree.range[0]];713                    comments.push(comment);714                }715                tree.leadingComments = comments;716            }717            return tree;718        }719 720        for (i = 0, len = providedComments.length; i < len; i += 1) {721            comments.push(extendCommentRange(deepCopy(providedComments[i]), tokens));722        }723 724        // This is based on John Freeman's implementation.725        cursor = 0;726        traverse(tree, {727            enter: function (node) {728                var comment;729 730                while (cursor < comments.length) {731                    comment = comments[cursor];732                    if (comment.extendedRange[1] > node.range[0]) {733                        break;734                    }735 736                    if (comment.extendedRange[1] === node.range[0]) {737                        if (!node.leadingComments) {738                            node.leadingComments = [];739                        }740                        node.leadingComments.push(comment);741                        comments.splice(cursor, 1);742                    } else {743                        cursor += 1;744                    }745                }746 747                // already out of owned node748                if (cursor === comments.length) {749                    return VisitorOption.Break;750                }751 752                if (comments[cursor].extendedRange[0] > node.range[1]) {753                    return VisitorOption.Skip;754                }755            }756        });757 758        cursor = 0;759        traverse(tree, {760            leave: function (node) {761                var comment;762 763                while (cursor < comments.length) {764                    comment = comments[cursor];765                    if (node.range[1] < comment.extendedRange[0]) {766                        break;767                    }768 769                    if (node.range[1] === comment.extendedRange[0]) {770                        if (!node.trailingComments) {771                            node.trailingComments = [];772                        }773                        node.trailingComments.push(comment);774                        comments.splice(cursor, 1);775                    } else {776                        cursor += 1;777                    }778                }779 780                // already out of owned node781                if (cursor === comments.length) {782                    return VisitorOption.Break;783                }784 785                if (comments[cursor].extendedRange[0] > node.range[1]) {786                    return VisitorOption.Skip;787                }788            }789        });790 791        return tree;792    }793 794    exports.Syntax = Syntax;795    exports.traverse = traverse;796    exports.replace = replace;797    exports.attachComments = attachComments;798    exports.VisitorKeys = VisitorKeys;799    exports.VisitorOption = VisitorOption;800    exports.Controller = Controller;801    exports.cloneEnvironment = function () { return clone({}); };802 803    return exports;804}(exports));805/* vim: set sw=4 ts=4 et tw=80 : */806