Erlang Plugin for NetBeans in Scala#5: Structure Analyzer

During the weekend, I've done some preliminary error recover work for Erlang's rats! definition. Now I'll go on some features based on analysis on AST tree. As the simplest step, we'll visit/analyze AST tree to get the structure information, use them for Navigator window and code folding.

First, we need to record the Structure information in some way. Each language has different AST tree and may be generated by varies tools, the AST element should be wrapped in some more generic classes to get integrated into CSL framework. There is an interface "org.netbeans.modules.csl.api.ElementKind", which is used for this purpose. But it's not enough, we need some facilities to not only wrap AST element, and also help us to identify the element as a definition or reference, in which visible scope etc.

I wrote a couple of these facilities when I wrote Erlang/Fortress/Scala plug-ins, these facilities can be repeatedly used for other languages by minor modifying. They are AstItem, AstDfn, AstRef, AstScope, AstRootScope. For Erlang plugin, you can find them under director: erlang.editor/src/org/netbeans/modules/erlang/editor/ast

AstDfn.scala is used to store a definition, such as definitions of class, module, method, variable, attribute etc. AstRef.scala is used to store reference that refers to definition, for example, the usages of a class, a variable, a method call etc.

All these AST items are stored in instances of AstScope.scala, which, is a container to identify the visible scope of references/definitions and store its sub-scopes. There are functions in AstScope to help to identify a variable's visible scope, find the definition of a reference, find references/occurrences of a definition etc.

There should be some lexer level utilities too, to help you get the corresponding tokens when you visit AST tree. It's LexUtil.scala, which will be also heavy used for code-folding, indentation ... features.

With above facilities, we can visit an AST tree now, I'll do the simplest task first: get all functions/attribues name and bounds tokens.

AstNodeVisitor.scala

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 * 
 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
 * 
 * The contents of this file are subject to the terms of either the GNU
 * General Public License Version 2 only ("GPL") or the Common
 * Development and Distribution License("CDDL") (collectively, the
 * "License"). You may not use this file except in compliance with the
 * License. You can obtain a copy of the License at
 * http://www.netbeans.org/cddl-gplv2.html
 * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
 * specific language governing permissions and limitations under the
 * License.  When distributing the software, include this License Header
 * Notice in each file and include the License file at
 * nbbuild/licenses/CDDL-GPL-2-CP.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun in the GPL Version 2 section of the License file that
 * accompanied this code. If applicable, add the following below the
 * License Header, with the fields enclosed by brackets [] replaced by
 * your own identifying information:
 * "Portions Copyrighted [year] [name of copyright owner]"
 * 
 * If you wish your version of this file to be governed by only the CDDL
 * or only the GPL Version 2, indicate your decision by adding
 * "[Contributor] elects to include this software in this distribution
 * under the [CDDL or GPL Version 2] license." If you do not indicate a
 * single choice of license, a recipient has the option to distribute
 * your version of this file under either the CDDL, the GPL Version 2 or
 * to extend the choice of license to its licensees as provided above.
 * However, if you add GPL Version 2 code and therefore, elected the GPL
 * Version 2 license, then the option applies only if the new code is
 * made subject to such option by the copyright holder.
 * 
 * Contributor(s):
 * 
 * Portions Copyrighted 2009 Sun Microsystems, Inc.
 */
package org.netbeans.modules.erlang.editor.node

import org.netbeans.api.lexer.{Token, TokenId, TokenHierarchy, TokenSequence}
import org.netbeans.modules.csl.api.ElementKind

import org.netbeans.modules.erlang.editor.ast.{AstDfn, AstItem, AstRef, AstRootScope, AstScope, AstVisitor}
import org.netbeans.modules.erlang.editor.lexer.ErlangTokenId._
import org.netbeans.modules.erlang.editor.lexer.{ErlangTokenId, LexUtil}
import org.openide.filesystems.FileObject

import scala.collection.mutable.ArrayBuffer

import xtc.tree.GNode
import xtc.tree.Node
import xtc.util.Pair

/**
 *
 * @author Caoyuan Deng
 */
class AstNodeVisitor(rootNode:Node, th:TokenHierarchy[_], fo:FileObject) extends AstVisitor(rootNode, th) {

    def visitS(that:GNode) = {
        val formNodes = that.getList(0).iterator
        while(formNodes.hasNext) {
            visitForm(formNodes.next)
        }
    }

    def visitForm(that:GNode) = {
        enter(that)

        val scope = new AstScope(boundsTokens(that))
        rootScope.addScope(scope)

        scopes.push(scope)
        visitNodeOnly(that.getGeneric(0))
        
        exit(that)
        scopes.pop
    }


    def visitAttribute(that:GNode) = {
        that.get(0) match {
            case atomId:GNode =>
                val attr = new AstDfn(that, idToken(idNode(atomId)), scopes.top, ElementKind.ATTRIBUTE, fo)
                rootScope.addDfn(attr)
        }
    }

    def visitFunction(that:GNode) = {
        visitFunctionClauses(that.getGeneric(0))
    }

    def visitFunctionClauses(that:GNode) = {
        val fstClauseNode = that.getGeneric(0)
        visitFunctionClause(fstClauseNode)
    }

    def visitFunctionClause(that:GNode) = {
        val id = idNode(that.getGeneric(0))
        val fun = new AstDfn(that, idToken(id), scopes.top, ElementKind.METHOD, fo)
        rootScope.addDfn(fun)
    }

    def visitRule(that:GNode) = {

    }
}

As you can see, I just visit function/attribute related AST nodes, and gather all function/attribute declarations (or, definitions). My AST tree is generated by rats!, so the code looks like above. If you are using other parsers, I assume you know of course how to travel it.

AstNodeVisitor extends AstVisitor, I wrote some helper methods in AstVisitor.scala, for example, getting the bounds tokens for a definition/scope.

Now, you need to put the AST visiting task to ErlangParser.scala, so, it will be called when parsing finished, and you'll get an AST tree. The code is something like:

    private def analyze(context:Context) :Unit = {
        val doc = LexUtil.document(context.snapshot, false)

        // * we need TokenHierarchy to do anaylzing task
        for (root <- context.root;
             th <- LexUtil.tokenHierarchy(context.snapshot)) {
            // * Due to Token hierarchy will be used in analyzing, should do it in an Read-lock atomic task
            for (x <- doc) {x.readLock}
            try {
                val visitor = new AstNodeVisitor(root, th, context.fo)
                visitor.visit(root)
                context.rootScope = Some(visitor.rootScope)
            } catch {
                case ex:Throwable => ex.printStackTrace
            } finally {
                for (x <- doc) {x.readUnlock}
            }
        }
    }

The rootScope will be carried in ErlangParserResult.scala.

With the visitor's rootScope, we can implement the navigator window and code folding now. What you need is to implement an org.netbeans.modules.csl.api.StructureScanner. My implementation is: ErlangStructureAnalyzer.scala

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
 *
 * The contents of this file are subject to the terms of either the GNU
 * General Public License Version 2 only ("GPL") or the Common
 * Development and Distribution License("CDDL") (collectively, the
 * "License"). You may not use this file except in compliance with the
 * License. You can obtain a copy of the License at
 * http://www.netbeans.org/cddl-gplv2.html
 * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
 * specific language governing permissions and limitations under the
 * License.  When distributing the software, include this License Header
 * Notice in each file and include the License file at
 * nbbuild/licenses/CDDL-GPL-2-CP.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun in the GPL Version 2 section of the License file that
 * accompanied this code. If applicable, add the following below the
 * License Header, with the fields enclosed by brackets [] replaced by
 * your own identifying information:
 * "Portions Copyrighted [year] [name of copyright owner]"
 *
 * If you wish your version of this file to be governed by only the CDDL
 * or only the GPL Version 2, indicate your decision by adding
 * "[Contributor] elects to include this software in this distribution
 * under the [CDDL or GPL Version 2] license." If you do not indicate a
 * single choice of license, a recipient has the option to distribute
 * your version of this file under either the CDDL, the GPL Version 2 or
 * to extend the choice of license to its licensees as provided above.
 * However, if you add GPL Version 2 code and therefore, elected the GPL
 * Version 2 license, then the option applies only if the new code is
 * made subject to such option by the copyright holder.
 *
 * Contributor(s):
 *
 * Portions Copyrighted 2009 Sun Microsystems, Inc.
 */
package org.netbeans.modules.erlang.editor;

import _root_.java.util.{ArrayList,Collections,HashMap,List,Map,Set,Stack}
import javax.swing.ImageIcon;
import javax.swing.text.{BadLocationException,Document}
import org.netbeans.api.lexer.{Token,TokenId,TokenHierarchy,TokenSequence}
import org.netbeans.editor.{BaseDocument,Utilities}
import org.netbeans.modules.csl.api.{ElementHandle,ElementKind,HtmlFormatter,Modifier,OffsetRange,StructureItem,StructureScanner}
import org.netbeans.modules.csl.api.StructureScanner._
import org.netbeans.modules.csl.spi.ParserResult
import org.netbeans.modules.erlang.editor.ast.{AstDfn,AstRootScope,AstScope}
import org.netbeans.modules.erlang.editor.lexer.{ErlangTokenId,LexUtil}
import org.openide.util.Exceptions

import scala.collection.mutable.ArrayBuffer

/**
 *
 * @author Caoyuan Deng
 */
class ErlangStructureAnalyzer extends StructureScanner {

    override
    def getConfiguration :Configuration = null

    override
    def scan(result:ParserResult) :List[StructureItem] = result match {
        case null => Collections.emptyList[StructureItem]
        case pResult:ErlangParserResult => 
            var items = Collections.emptyList[StructureItem]
            for (rootScope <- pResult.rootScope) {
                items = new ArrayList[StructureItem](rootScope.dfns.size)
                scanTopForms(rootScope, items, pResult)
            }
            items
    }

    private def scanTopForms(scope:AstScope, items:List[StructureItem], pResult:ErlangParserResult) :Unit = {
        for (dfn <- scope.dfns) {
            dfn.getKind match {
                case ElementKind.ATTRIBUTE | ElementKind.METHOD => items.add(new ErlangStructureItem(dfn, pResult))
                case _ =>
            }
            scanTopForms(dfn.bindingScope, items, pResult)
        }
    }

    override
    def folds(result:ParserResult) :Map[String, List[OffsetRange]] = result match {
        case null => Collections.emptyMap[String, List[OffsetRange]]
        case pResult:ErlangParserResult =>
            var folds = Collections.emptyMap[String, List[OffsetRange]]
            for (rootScope <- pResult.rootScope;
                 doc <- LexUtil.document(pResult, true);
                 th <- LexUtil.tokenHierarchy(pResult);
                 ts <- LexUtil.tokenSequence(th, 1)
            ) {
                folds = new HashMap[String, List[OffsetRange]]
                val codefolds = new ArrayList[OffsetRange]
                folds.put("codeblocks", codefolds); // NOI18N

                // * Read-lock due to Token hierarchy use
                doc.readLock

                addCodeFolds(pResult, doc, rootScope.dfns, codefolds)

                var lineCommentStart = 0
                var lineCommentEnd = 0
                var startLineCommentSet = false

                val comments = new Stack[Array[Integer]]
                val blocks = new Stack[Integer]

                while (ts.isValid && ts.moveNext) {
                    val token = ts.token
                    token.id match {
                        case ErlangTokenId.LineComment =>
                            val offset = ts.offset
                            if (!startLineCommentSet) {
                                lineCommentStart = offset
                                startLineCommentSet = true
                            }
                            lineCommentEnd = offset

                        case ErlangTokenId.Case | ErlangTokenId.If | ErlangTokenId.Try | ErlangTokenId.Receive =>
                            val blockStart = ts.offset
                            blocks.push(blockStart)

                            startLineCommentSet = false
                        
                        case ErlangTokenId.End if !blocks.empty =>
                            val blockStart = blocks.pop.asInstanceOf[Int]
                            val blockRange = new OffsetRange(blockStart, ts.offset + token.length)
                            codefolds.add(blockRange)

                            startLineCommentSet = false
                        case _ =>
                            startLineCommentSet = false
                    }
                }

                doc.readUnlock

                try {
                    /** @see GsfFoldManager#addTree() for suitable fold names. */
                    lineCommentEnd = Utilities.getRowEnd(doc, lineCommentEnd)

                    if (Utilities.getRowCount(doc, lineCommentStart, lineCommentEnd) > 1) {
                        val lineCommentsFolds = new ArrayList[OffsetRange];
                        val range = new OffsetRange(lineCommentStart, lineCommentEnd)
                        lineCommentsFolds.add(range)
                        folds.put("comments", lineCommentsFolds) // NOI18N
                    }
                } catch {
                    case ex:BadLocationException => Exceptions.printStackTrace(ex)
                }
            }

            folds
    }

    @throws(classOf[BadLocationException])
    private def addCodeFolds(pResult:ErlangParserResult, doc:BaseDocument, defs:ArrayBuffer[AstDfn], codeblocks:List[OffsetRange]) :Unit = {
        import ElementKind._
       
        for (dfn <- defs) {
            val kind = dfn.getKind
            kind match {
                case FIELD | METHOD | CONSTRUCTOR | CLASS | MODULE | ATTRIBUTE =>
                    var range = dfn.getOffsetRange(pResult)
                    var start = range.getStart
                    // * start the fold at the end of the line behind last non-whitespace, should add 1 to start after "->"
                    start = Utilities.getRowLastNonWhite(doc, start) + 1
                    val end = range.getEnd
                    if (start != -1 && end != -1 && start < end && end <= doc.getLength) {
                        range = new OffsetRange(start, end)
                        codeblocks.add(range)
                    }
                case _ =>
            }
    
            val children = dfn.bindingScope.dfns
            addCodeFolds(pResult, doc, children, codeblocks)
        }
    }

    private class ErlangStructureItem(val dfn:AstDfn, pResult:ParserResult) extends StructureItem {
        import ElementKind._

        override
        def getName :String = dfn.getName

        override
        def getSortText :String = getName

        override
        def getHtml(formatter:HtmlFormatter) :String = {
            dfn.htmlFormat(formatter)
            formatter.getText
        }

        override
        def getElementHandle :ElementHandle = dfn

        override
        def getKind :ElementKind = dfn.getKind
        
        override
        def getModifiers :Set[Modifier] = dfn.getModifiers

        override
        def isLeaf :Boolean = dfn.getKind match {
            case MODULE | CLASS => false
            case CONSTRUCTOR | METHOD | FIELD | VARIABLE | OTHER | PARAMETER | ATTRIBUTE => true
            case _ => true
        }

        override
        def getNestedItems : List[StructureItem] = {
            val nested = dfn.bindingScope.dfns
            if (nested.size > 0) {
                val children = new ArrayList[StructureItem](nested.size)

                for (child <- nested) {
                    child.kind match {
                        case PARAMETER | VARIABLE | OTHER =>
                        case _ => children.add(new ErlangStructureItem(child, pResult))
                    }
                }

                children
            } else Collections.emptyList[StructureItem]
        }

        override
        def getPosition :Long = {
            try {
                LexUtil.tokenHierarchy(pResult) match {
                    case None => 0
                    case Some(th) => dfn.boundsOffset(th)
                }
            } catch {case ex:Exception => 0}
        }

        override
        def getEndPosition :Long = {
            try {
                LexUtil.tokenHierarchy(pResult) match {
                    case None => 0
                    case Some(th) => dfn.boundsEndOffset(th)
                }
            } catch {case ex:Exception => 0}
        }

        override
        def equals(o:Any) :Boolean = o match {
            case null => false
            case x:ErlangStructureItem if dfn.getKind == x.dfn.getKind && getName.equals(x.getName) => true
            case _ => false
        }

        override
        def hashCode :Int = {
            var hash = 7
            hash = (29 * hash) + (if (getName != null) getName.hashCode else 0)
            hash = (29 * hash) + (if (dfn.getKind != null) dfn.getKind.hashCode else 0)
            hash
        }

        override
        def toString = getName

        override
        def getCustomIcon :ImageIcon = null
    }
}

Which just travels the rootScope, fetches AstDfn's instances and wrap them to ErlangStructureItem.

The last step is register this structure analyzer to ErlangLanguage.Scala as usual:

    override
    def hasStructureScanner = true

    override
    def getStructureScanner = new ErlangStructureAnalyzer

For structure analyzer, you need also to register it in layer.xml:

    <folder name="CslPlugins">
        <folder name="text">
            <folder name="x-erlang">
                <file name="language.instance">
                    <attr name="instanceClass" stringvalue="org.netbeans.modules.erlang.editor.ErlangLanguage"/>
                </file>
                <file name="structure.instance">
                    <attr name="instanceClass" stringvalue="org.netbeans.modules.erlang.editor.ErlangStructureAnalyzer"/>
                </file>
            </folder>
        </folder>
    </folder>

Build and run, now open a .erl file, you got:

Click on the picture to enlarge it

nn

The functions/attributes are shown in the left-side navigator window now, there are also some code-folding marks. Did you notice my preliminaty error-recover work? :-)

Comments

No comments.