helper.go 7.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347
  1. /*
  2. * Public Domain Software
  3. *
  4. * I (Matthias Ladkau) am the author of the source code in this file.
  5. * I have placed the source code in this file in the public domain.
  6. *
  7. * For further information see: http://creativecommons.org/publicdomain/zero/1.0/
  8. */
  9. package parser
  10. import (
  11. "bytes"
  12. "fmt"
  13. "strconv"
  14. "devt.de/krotik/common/datautil"
  15. "devt.de/krotik/common/stringutil"
  16. )
  17. // AST Nodes
  18. // =========
  19. /*
  20. ASTNode models a node in the AST
  21. */
  22. type ASTNode struct {
  23. Name string // Name of the node
  24. Token *LexToken // Lexer token of this ASTNode
  25. Children []*ASTNode // Child nodes
  26. Runtime Runtime // Runtime component for this ASTNode
  27. binding int // Binding power of this node
  28. nullDenotation func(p *parser, self *ASTNode) (*ASTNode, error) // Configure token as beginning node
  29. leftDenotation func(p *parser, self *ASTNode, left *ASTNode) (*ASTNode, error) // Configure token as left node
  30. }
  31. /*
  32. Create a new instance of this ASTNode which is connected to a concrete lexer token.
  33. */
  34. func (n *ASTNode) instance(p *parser, t *LexToken) *ASTNode {
  35. ret := &ASTNode{n.Name, t, make([]*ASTNode, 0, 2), nil, n.binding, n.nullDenotation, n.leftDenotation}
  36. if p.rp != nil {
  37. ret.Runtime = p.rp.Runtime(ret)
  38. }
  39. return ret
  40. }
  41. /*
  42. Equal checks if this AST data equals another AST data. Returns also a message describing
  43. what is the found difference.
  44. */
  45. func (n *ASTNode) Equals(other *ASTNode) (bool, string) {
  46. return n.equalsPath(n.Name, other)
  47. }
  48. /*
  49. equalsPath checks if this AST data equals another AST data while preserving the search path.
  50. Returns also a message describing what is the found difference.
  51. */
  52. func (n *ASTNode) equalsPath(path string, other *ASTNode) (bool, string) {
  53. var res = true
  54. var msg = ""
  55. if n.Name != other.Name {
  56. res = false
  57. msg = fmt.Sprintf("Name is different %v vs %v\n", n.Name, other.Name)
  58. }
  59. if ok, tokenMSG := n.Token.Equals(*other.Token); !ok {
  60. res = false
  61. msg += fmt.Sprintf("Token is different:\n%v\n", tokenMSG)
  62. }
  63. if len(n.Children) != len(other.Children) {
  64. res = false
  65. msg = fmt.Sprintf("Number of children is different %v vs %v\n",
  66. len(n.Children), len(other.Children))
  67. } else {
  68. for i, child := range n.Children {
  69. // Check for different in children
  70. if ok, childMSG := child.equalsPath(fmt.Sprintf("%v > %v", path, child.Name),
  71. other.Children[i]); !ok {
  72. return ok, childMSG
  73. }
  74. }
  75. }
  76. if msg != "" {
  77. var buf bytes.Buffer
  78. buf.WriteString("AST Nodes:\n")
  79. n.levelString(0, &buf, 1)
  80. buf.WriteString("vs\n")
  81. other.levelString(0, &buf, 1)
  82. msg = fmt.Sprintf("Path to difference: %v\n\n%v\n%v", path, msg, buf.String())
  83. }
  84. return res, msg
  85. }
  86. /*
  87. String returns a string representation of this token.
  88. */
  89. func (n *ASTNode) String() string {
  90. var buf bytes.Buffer
  91. n.levelString(0, &buf, -1)
  92. return buf.String()
  93. }
  94. /*
  95. levelString function to recursively print the tree.
  96. */
  97. func (n *ASTNode) levelString(indent int, buf *bytes.Buffer, printChildren int) {
  98. // Print current level
  99. buf.WriteString(stringutil.GenerateRollingString(" ", indent*2))
  100. if n.Name == NodeCOMMENT {
  101. buf.WriteString(fmt.Sprintf("%v: %20v", n.Name, n.Token.Val))
  102. } else if n.Name == NodeSTRING {
  103. buf.WriteString(fmt.Sprintf("%v: '%v'", n.Name, n.Token.Val))
  104. } else if n.Name == NodeNUMBER {
  105. buf.WriteString(fmt.Sprintf("%v: %v", n.Name, n.Token.Val))
  106. } else if n.Name == NodeIDENTIFIER {
  107. buf.WriteString(fmt.Sprintf("%v: %v", n.Name, n.Token.Val))
  108. } else {
  109. buf.WriteString(n.Name)
  110. }
  111. buf.WriteString("\n")
  112. if printChildren == -1 || printChildren > 0 {
  113. if printChildren != -1 {
  114. printChildren--
  115. }
  116. // Print children
  117. for _, child := range n.Children {
  118. child.levelString(indent+1, buf, printChildren)
  119. }
  120. }
  121. }
  122. /*
  123. ToJSON returns this ASTNode and all its children as a JSON object.
  124. */
  125. func (n *ASTNode) ToJSONObject() map[string]interface{} {
  126. ret := make(map[string]interface{})
  127. ret["name"] = n.Name
  128. lenChildren := len(n.Children)
  129. if lenChildren > 0 {
  130. children := make([]map[string]interface{}, lenChildren)
  131. for i, child := range n.Children {
  132. children[i] = child.ToJSONObject()
  133. }
  134. ret["children"] = children
  135. }
  136. // The value is what the lexer found in the source
  137. if n.Token != nil {
  138. ret["id"] = n.Token.ID
  139. if n.Token.Val != "" {
  140. ret["value"] = n.Token.Val
  141. }
  142. ret["identifier"] = n.Token.Identifier
  143. ret["pos"] = n.Token.Pos
  144. ret["line"] = n.Token.Lline
  145. ret["linepos"] = n.Token.Lpos
  146. }
  147. return ret
  148. }
  149. /*
  150. ASTFromPlain creates an AST from a JSON Object.
  151. The following nested map structure is expected:
  152. {
  153. name : <name of node>
  154. // Optional node information
  155. value : <value of node>
  156. children : [ <child nodes> ]
  157. // Optional token information
  158. id : <token id>
  159. }
  160. */
  161. func ASTFromJSONObject(jsonAST map[string]interface{}) (*ASTNode, error) {
  162. var astChildren []*ASTNode
  163. var nodeID LexTokenID = TokenANY
  164. var pos, line, linepos int
  165. name, ok := jsonAST["name"]
  166. if !ok {
  167. return nil, fmt.Errorf("Found json ast node without a name: %v", jsonAST)
  168. }
  169. if nodeIDString, ok := jsonAST["id"]; ok {
  170. if nodeIDInt, err := strconv.Atoi(fmt.Sprint(nodeIDString)); err == nil && IsValidTokenID(nodeIDInt) {
  171. nodeID = LexTokenID(nodeIDInt)
  172. }
  173. }
  174. value, ok := jsonAST["value"]
  175. if !ok {
  176. value = ""
  177. }
  178. identifier, ok := jsonAST["identifier"]
  179. if !ok {
  180. identifier = false
  181. }
  182. if posString, ok := jsonAST["pos"]; ok {
  183. pos, _ = strconv.Atoi(fmt.Sprint(posString))
  184. } else {
  185. pos = 0
  186. }
  187. if lineString, ok := jsonAST["line"]; ok {
  188. line, _ = strconv.Atoi(fmt.Sprint(lineString))
  189. } else {
  190. line = 0
  191. }
  192. if lineposString, ok := jsonAST["linepos"]; ok {
  193. linepos, _ = strconv.Atoi(fmt.Sprint(lineposString))
  194. } else {
  195. linepos = 0
  196. }
  197. // Create children
  198. if children, ok := jsonAST["children"]; ok {
  199. if ic, ok := children.([]interface{}); ok {
  200. // Do a list conversion if necessary - this is necessary when we parse
  201. // JSON with map[string]interface{}
  202. childrenList := make([]map[string]interface{}, len(ic))
  203. for i := range ic {
  204. childrenList[i] = ic[i].(map[string]interface{})
  205. }
  206. children = childrenList
  207. }
  208. for _, child := range children.([]map[string]interface{}) {
  209. astChild, err := ASTFromJSONObject(child)
  210. if err != nil {
  211. return nil, err
  212. }
  213. astChildren = append(astChildren, astChild)
  214. }
  215. }
  216. token := &LexToken{
  217. nodeID, // ID
  218. pos, // Pos
  219. fmt.Sprint(value), // Val
  220. identifier == true, // Identifier
  221. line, // Lline
  222. linepos, // Lpos
  223. }
  224. return &ASTNode{fmt.Sprint(name), token, astChildren, nil, 0, nil, nil}, nil
  225. }
  226. // Look ahead buffer
  227. // =================
  228. /*
  229. ASTNode models a node in the AST
  230. */
  231. type LABuffer struct {
  232. tokens chan LexToken
  233. buffer *datautil.RingBuffer
  234. }
  235. /*
  236. Create a new instance of this ASTNode which is connected to a concrete lexer token.
  237. */
  238. func NewLABuffer(c chan LexToken, size int) *LABuffer {
  239. if size < 1 {
  240. size = 1
  241. }
  242. ret := &LABuffer{c, datautil.NewRingBuffer(size)}
  243. v, more := <-ret.tokens
  244. ret.buffer.Add(v)
  245. for ret.buffer.Size() < size && more && v.ID != TokenEOF {
  246. v, more = <-ret.tokens
  247. ret.buffer.Add(v)
  248. }
  249. return ret
  250. }
  251. /*
  252. Next returns the next item.
  253. */
  254. func (b *LABuffer) Next() (LexToken, bool) {
  255. ret := b.buffer.Poll()
  256. if v, more := <-b.tokens; more {
  257. b.buffer.Add(v)
  258. }
  259. if ret == nil {
  260. return LexToken{ID: TokenEOF}, false
  261. }
  262. return ret.(LexToken), true
  263. }
  264. /*
  265. Peek looks inside the buffer starting with 0 as the next item.
  266. */
  267. func (b *LABuffer) Peek(pos int) (LexToken, bool) {
  268. if pos >= b.buffer.Size() {
  269. return LexToken{ID: TokenEOF}, false
  270. }
  271. return b.buffer.Get(pos).(LexToken), true
  272. }