Line data    Source code

       1             : // Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
       2             : // of this source code is governed by a BSD-style license that can be found in
       3             : // the LICENSE file.
       4             : 
       5             : // Package indenttree implements a simple text processor which parses a
       6             : // hierarchy defined using indentation; see Parse.
       7             : package indenttree
       8             : 
       9             : import (
      10             :         "slices"
      11             :         "strings"
      12             : 
      13             :         "github.com/cockroachdb/errors"
      14             : )
      15             : 
      16             : // Parse a multi-line input string into trees of nodes. For example:
      17             : //
      18             : //      a
      19             : //       a1
      20             : //        a11
      21             : //       a2
      22             : //      b
      23             : //       b1
      24             : //
      25             : // is parsed into two Nodes (a and b). Node a has two children (a1, a2), and a2
      26             : // has one child (a11); node b has one child (b1).
      27             : //
      28             : // The indentation level is arbitrary but it must be consistent. across nodes. For example, the following is not valid:
      29             : //
      30             : //      a
      31             : //       a1
      32             : //      b
      33             : //        b1
      34             : //
      35             : // Tabs cannot be used for indentation (they can cause confusion if editor
      36             : // settings vary). Nodes cannot be skipped, for example the following is not
      37             : // valid:
      38             : //
      39             : //      a
      40             : //        a1
      41             : //          a11
      42             : //      b
      43             : //          b12
      44           1 : func Parse(input string) ([]Node, error) {
      45           1 :         input = strings.TrimSuffix(input, "\n")
      46           1 :         if input == "" {
      47           1 :                 return nil, errors.Errorf("empty input")
      48           1 :         }
      49           1 :         lines := strings.Split(input, "\n")
      50           1 :         indentLevel := make([]int, len(lines))
      51           1 :         for i, line := range lines {
      52           1 :                 level := 0
      53           1 :                 for strings.HasPrefix(line[level:], " ") {
      54           1 :                         level++
      55           1 :                 }
      56           1 :                 if len(line) == level {
      57           0 :                         return nil, errors.Errorf("empty line in input:\n%s", input)
      58           0 :                 }
      59           1 :                 if line[level] == '\t' {
      60           0 :                         return nil, errors.Errorf("tab indentation in input:\n%s", input)
      61           0 :                 }
      62           1 :                 indentLevel[i] = level
      63             :         }
      64           1 :         levels := slices.Clone(indentLevel)
      65           1 :         slices.Sort(levels)
      66           1 :         levels = slices.Compact(levels)
      67           1 : 
      68           1 :         var parse func(levelIdx, startLineIdx, endLineIdx int) ([]Node, error)
      69           1 :         parse = func(levelIdx, startLineIdx, endLineIdx int) ([]Node, error) {
      70           1 :                 if startLineIdx > endLineIdx {
      71           1 :                         return nil, nil
      72           1 :                 }
      73           1 :                 level := levels[levelIdx]
      74           1 :                 if indentLevel[startLineIdx] != level {
      75           1 :                         return nil, errors.Errorf("inconsistent indentation in input:\n%s", input)
      76           1 :                 }
      77           1 :                 nextNode := startLineIdx + 1
      78           1 :                 for ; nextNode <= endLineIdx; nextNode++ {
      79           1 :                         if indentLevel[nextNode] <= level {
      80           1 :                                 break
      81             :                         }
      82             :                 }
      83           1 :                 node := Node{value: lines[startLineIdx][level:]}
      84           1 :                 var err error
      85           1 :                 node.children, err = parse(levelIdx+1, startLineIdx+1, nextNode-1)
      86           1 :                 if err != nil {
      87           1 :                         return nil, err
      88           1 :                 }
      89           1 :                 otherNodes, err := parse(levelIdx, nextNode, endLineIdx)
      90           1 :                 if err != nil {
      91           1 :                         return nil, err
      92           1 :                 }
      93           1 :                 return append([]Node{node}, otherNodes...), nil
      94             :         }
      95           1 :         return parse(0, 0, len(lines)-1)
      96             : }
      97             : 
      98             : // Node in a hierarchy returned by Parse.
      99             : type Node struct {
     100             :         value    string
     101             :         children []Node
     102             : }
     103             : 
     104             : // Value returns the contents of the line for this node (without the
     105             : // indentation).
     106           1 : func (n *Node) Value() string {
     107           1 :         return n.value
     108           1 : }
     109             : 
     110             : // Children returns the child nodes, if any.
     111           1 : func (n *Node) Children() []Node {
     112           1 :         return n.children
     113           1 : }