[C#] ASTNode Span and Positions = 0

[woutersl]

Original report by Goomba (Bitbucket: 5a6bdc01c10afd5fcdd933bf, GitHub: raizam).

---

Hi, I'm having an issue that I don't think I had before, using the rnglr parser, ASTNodes don't have Span and Positions values initialized. I reverted to version 3.3.1 but I'm still having that issue.

[woutersl]

Original comment by Laurent Wouters (Bitbucket: 557058:675792b6-d731-4823-9f7d-c6dfcb2df2b5, ).

---

That is very weird, sorry for the trouble.

What platform are you using ? .Net Framework or .NetCore ?

Also are you positive that you are looking at AST nodes that hold tokens ? AST nodes that hold variables or (virtual symbols) indeed have a default Span and Position of 0, since they have no meaning for them (for a variety of reasons).

[woutersl]

Original comment by Goomba (Bitbucket: 5a6bdc01c10afd5fcdd933bf, GitHub: raizam).

---

Yes I realized variables don't hold position/span afterwards, sorry it's been a long time I haven't used Hime.

Here is what I ended up doing, changing the ASTNode implementation:

#!c#

        /// <summary>
        /// Gets the position in the input text of this node
        /// </summary>
        public TextPosition Position
        {
            get
            {
                if (SymbolType != SymbolType.Terminal && Children.Count > 0)
                    return Children[0].Position;
                return tree.GetPosition(index);
            }
        }

        /// <summary>
        /// Gets the span in the input text of this node
        /// </summary>
        public TextSpan Span
        {
            get
            {
                if (SymbolType != SymbolType.Terminal && Children.Count > 0)
                {
                    if (Children.Count > 1)
                    {
                        var idx = Children[0].Span.Index;
                        var lastSpan = Children[Children.Count - 1].Span;
                        return new TextSpan(idx, lastSpan.Index - idx + lastSpan .Length);
                    }else
                    {
                        return Children[0].Span;
                    }
                }

                return tree.GetSpan(index);
            }
        }

        /// <summary>
        /// Gets the value of this node
        /// </summary>
        public string Value
        {
            get
            {
                if (SymbolType != SymbolType.Terminal && Children.Count == 1)
                {
                    return Children[0].Value;
                }
                return tree.GetValue(index);
            }
        }

[woutersl]

Original comment by Goomba (Bitbucket: 5a6bdc01c10afd5fcdd933bf, GitHub: raizam).

---

bon et sinon, tu veux pas passer à git pour que je puisse contribuer? :)

[woutersl]

Original comment by Laurent Wouters (Bitbucket: 557058:675792b6-d731-4823-9f7d-c6dfcb2df2b5, ).

---

Merci pour la proposition de changement ! J'avais pensé que ça pourrait être utile d'avoir Span et Position sur tous les noeuds de l'AST. Mais en fait le problème est assez complexe. La solution donnée n'est correcte que si on considère qu'il n'y a pas eu de manipulation de l'AST avec des opérations ^ et !. On peut facilement se retrouver avec des noeuds qui portent des tokens avec une position mais en fait ses propres enfants ont des positions avant et après simplement parce que le noeud a été promu depuis le milieu de la règle:

e -> x y^ z;

On va se retrouver avec une racine y et des enfants x et z. Dans l'absolu le problème est plus compliqué, mais en même temps la solution proposée est mieux que rien ...

Pour git je n'ai pas de contrainte idéologique, juste une problématique pratique, pour changer de mercurial à git en conservant l'url https://bitbucket.org/cenotelie/hime, il faut que je le supprime et le re-crée pour git; mais du coup je perd les tickets, en plus des gens qui avait mis en favori le repo ... Mais si c'est juste de temps en temps, tu peux soumettre le changeset en mode texte au format .patch, comme export du commit git, ça fonctionne normalement.

[woutersl]

Original comment by Goomba (Bitbucket: 5a6bdc01c10afd5fcdd933bf, GitHub: raizam).

---

oui j'ai réalisé ensuite que ça marchait pas avec un noeud contenant un drop. Mais puisqu'aucune opération ne supprime des noeuds parents, n'est-il pas possible de calculer les Span/Position des parents avant d'appliquer les opérations sur l'AST? J'en ai besoin pour pouvoir mettre en surbrillance des expressions complètes avec une extension VsCode.

[woutersl]

Original comment by Laurent Wouters (Bitbucket: 557058:675792b6-d731-4823-9f7d-c6dfcb2df2b5, ).

---

Dans l'idée, oui; sauf que l'information n'est pas stockée sur le noeud mais est relative au token et est stockée dans une autre structure en dehors de l'AST (TokenRepository). Pour que cela fonctionne in faudrait revoir en profondeur le modèle de données de l'AST ...

Je pense que la solution intermédiaire proposée est un bon début, même si on sait qu'elle n'est pas parfaite. Typiquement dans le cas d'une grammaire d'expressions, on aurait envie d'avoir les opérateurs comme racine du sous-AST de la sous-expression correspondante. Mais dans ce cas le Span correspondrait uniquement au token de l'opérateur. Pour améliorer ce cas on pourrait dans le cas du Span pour un token sur un noeud qui n'est pas une feuille et a donc forcément été promu, essayer de calculer le Span de sous-arbre en regardant les enfants ...

Je vais continuer à y réfléchir quand j'aurai le temps. Est-ce que tu as besoin d'une version stable ou est-ce que la modif à la main des sources suffit pour l'instant pour résoudre ton problème ? Je pense que l'on peut intégrer cette modif dans un premier temps; cela ne devrait pas casser grand chose étant donnée que pour l'instant il n'y a pas de solution du tout.

[woutersl]

Original comment by Goomba (Bitbucket: 5a6bdc01c10afd5fcdd933bf, GitHub: raizam).

---

Je pense que pour ma part que cette approche va faire l'affaire. voici une version ajustée qui prend en compte les Promotes, qui semble bien marcher. La selection ne sera tronquée que lorsqu'il y a des drops aux extrémités. A noter que dans le cas d'un promote d'un terminal, c'est la position de ce terminal qui est renvoyé.

Si tu peux l'intégrer c'est tant mieux, ça va m'éviter de me retrouver avec un fork :)

#!c#

        /// <summary>
        /// Gets the position in the input text of this node
        /// </summary>
        public TextPosition Position
        {
            get
            {
                if (SymbolType != SymbolType.Terminal && Children.Count > 0)
                {
                    TextPosition minPosition = new TextPosition(); //default; //need to upgrade to c# 7.3
                    _computePositionRecursive(this, ref minPosition);
                    return minPosition;
                }

                return tree.GetPosition(index);
            }
        }

        void _computePositionRecursive(ASTNode node, ref TextPosition minPosition)
        {
            if (node.SymbolType == SymbolType.Terminal)
            {
                var currentPos = tree.GetPosition(node.index);

                //this works only if there's less than 2^16 lines or collumns
                uint minLineCollumn = ((uint)minPosition.Line << 16) | ((uint)minPosition.Column);
                uint currentLineCollumn = ((uint)currentPos.Line << 16) | ((uint)currentPos.Column);

                if (minPosition.Line == 0 || currentLineCollumn < minLineCollumn)
                    minPosition = currentPos;

            }
            else
            {
                for (int i = 0; i < node.Children.Count; i++)
                    _computePositionRecursive(node.Children[i], ref minPosition);
            }
        }

        void _computeSpanRecursive(ASTNode node, ref int minIndex, ref TextSpan lastSpan)
        {
            if (node.SymbolType == SymbolType.Terminal)
            {
                var thisSpan = tree.GetSpan(node.index);

                if (thisSpan.Length > 0 && (minIndex == 0 || thisSpan.Index < minIndex))
                    minIndex = thisSpan.Index;

                if (thisSpan.Index > lastSpan.Index)
                    lastSpan = thisSpan;
            }
            else
            {
                for (int i = 0; i < node.Children.Count; i++)
                {
                    _computeSpanRecursive(node.Children[i], ref minIndex, ref lastSpan);
                }
            }
        }

        /// <summary>
        /// Gets the span in the input text of this node
        /// </summary>
        public TextSpan Span
        {
            get
            {
                if (SymbolType != SymbolType.Terminal && Children.Count > 0)
                {
                    var outSpan = new TextSpan();
                    int idx = 0;
                    _computeSpanRecursive(this, ref idx, ref outSpan);

                    return new TextSpan(idx, (outSpan.Index - idx) + outSpan.Length);
                }
                return tree.GetSpan(index);

            }
        }

        /// <summary>
        /// Gets the value of this node
        /// </summary>
        public string Value
        {
            get
            {
                if (SymbolType != SymbolType.Terminal && Children.Count == 1)
                {
                    return Children[0].Value;
                }
                return tree.GetValue(index);
            }
        }