helper.go 9.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447
  1. /*
  2. * ECAL
  3. *
  4. * Copyright 2020 Matthias Ladkau. All rights reserved.
  5. *
  6. * This Source Code Form is subject to the terms of the MIT
  7. * License, If a copy of the MIT License was not distributed with this
  8. * file, You can obtain one at https://opensource.org/licenses/MIT.
  9. */
  10. package parser
  11. import (
  12. "bytes"
  13. "fmt"
  14. "strconv"
  15. "devt.de/krotik/common/datautil"
  16. "devt.de/krotik/common/stringutil"
  17. )
  18. // AST Nodes
  19. // =========
  20. /*
  21. MetaData is auxiliary data which can be attached to ASTs.
  22. */
  23. type MetaData interface {
  24. /*
  25. Type returns the type of the meta data.
  26. */
  27. Type() string
  28. /*
  29. Value returns the value of the meta data.
  30. */
  31. Value() string
  32. }
  33. /*
  34. metaData is a minimal MetaData implementation.
  35. */
  36. type metaData struct {
  37. metatype string
  38. metavalue string
  39. }
  40. /*
  41. Type returns the type of the meta data.
  42. */
  43. func (m *metaData) Type() string {
  44. return m.metatype
  45. }
  46. /*
  47. Value returns the value of the meta data.
  48. */
  49. func (m *metaData) Value() string {
  50. return m.metavalue
  51. }
  52. /*
  53. ASTNode models a node in the AST
  54. */
  55. type ASTNode struct {
  56. Name string // Name of the node
  57. Token *LexToken // Lexer token of this ASTNode
  58. Meta []MetaData // Meta data for this ASTNode (e.g. comments)
  59. Children []*ASTNode // Child nodes
  60. Runtime Runtime // Runtime component for this ASTNode
  61. binding int // Binding power of this node
  62. nullDenotation func(p *parser, self *ASTNode) (*ASTNode, error) // Configure token as beginning node
  63. leftDenotation func(p *parser, self *ASTNode, left *ASTNode) (*ASTNode, error) // Configure token as left node
  64. }
  65. /*
  66. Create a new instance of this ASTNode which is connected to a concrete lexer token.
  67. */
  68. func (n *ASTNode) instance(p *parser, t *LexToken) *ASTNode {
  69. ret := &ASTNode{n.Name, t, nil, make([]*ASTNode, 0, 2), nil, n.binding, n.nullDenotation, n.leftDenotation}
  70. if p.rp != nil {
  71. ret.Runtime = p.rp.Runtime(ret)
  72. }
  73. return ret
  74. }
  75. /*
  76. Equals checks if this AST data equals another AST data. Returns also a message describing
  77. what is the found difference.
  78. */
  79. func (n *ASTNode) Equals(other *ASTNode, ignoreTokenPosition bool) (bool, string) {
  80. return n.equalsPath(n.Name, other, ignoreTokenPosition)
  81. }
  82. /*
  83. equalsPath checks if this AST data equals another AST data while preserving the search path.
  84. Returns also a message describing what is the found difference.
  85. */
  86. func (n *ASTNode) equalsPath(path string, other *ASTNode, ignoreTokenPosition bool) (bool, string) {
  87. var res = true
  88. var msg = ""
  89. if n.Name != other.Name {
  90. res = false
  91. msg = fmt.Sprintf("Name is different %v vs %v\n", n.Name, other.Name)
  92. }
  93. if n.Token != nil && other.Token != nil {
  94. if ok, tokenMSG := n.Token.Equals(*other.Token, ignoreTokenPosition); !ok {
  95. res = false
  96. msg += fmt.Sprintf("Token is different:\n%v\n", tokenMSG)
  97. }
  98. }
  99. if len(n.Meta) != len(other.Meta) {
  100. res = false
  101. msg = fmt.Sprintf("Number of meta data entries is different %v vs %v\n",
  102. len(n.Meta), len(other.Meta))
  103. } else {
  104. for i, meta := range n.Meta {
  105. // Check for different in meta entries
  106. if meta.Type() != other.Meta[i].Type() {
  107. res = false
  108. msg += fmt.Sprintf("Meta data type is different %v vs %v\n", meta.Type(), other.Meta[i].Type())
  109. } else if meta.Value() != other.Meta[i].Value() {
  110. res = false
  111. msg += fmt.Sprintf("Meta data value is different %v vs %v\n", meta.Value(), other.Meta[i].Value())
  112. }
  113. }
  114. }
  115. if len(n.Children) != len(other.Children) {
  116. res = false
  117. msg = fmt.Sprintf("Number of children is different %v vs %v\n",
  118. len(n.Children), len(other.Children))
  119. } else {
  120. for i, child := range n.Children {
  121. // Check for different in children
  122. if ok, childMSG := child.equalsPath(fmt.Sprintf("%v > %v", path, child.Name),
  123. other.Children[i], ignoreTokenPosition); !ok {
  124. return ok, childMSG
  125. }
  126. }
  127. }
  128. if msg != "" {
  129. var buf bytes.Buffer
  130. buf.WriteString("AST Nodes:\n")
  131. n.levelString(0, &buf, 1)
  132. buf.WriteString("vs\n")
  133. other.levelString(0, &buf, 1)
  134. msg = fmt.Sprintf("Path to difference: %v\n\n%v\n%v", path, msg, buf.String())
  135. }
  136. return res, msg
  137. }
  138. /*
  139. String returns a string representation of this token.
  140. */
  141. func (n *ASTNode) String() string {
  142. var buf bytes.Buffer
  143. n.levelString(0, &buf, -1)
  144. return buf.String()
  145. }
  146. /*
  147. levelString function to recursively print the tree.
  148. */
  149. func (n *ASTNode) levelString(indent int, buf *bytes.Buffer, printChildren int) {
  150. // Print current level
  151. buf.WriteString(stringutil.GenerateRollingString(" ", indent*2))
  152. if n.Name == NodeSTRING {
  153. buf.WriteString(fmt.Sprintf("%v: '%v'", n.Name, n.Token.Val))
  154. } else if n.Name == NodeNUMBER {
  155. buf.WriteString(fmt.Sprintf("%v: %v", n.Name, n.Token.Val))
  156. } else if n.Name == NodeIDENTIFIER {
  157. buf.WriteString(fmt.Sprintf("%v: %v", n.Name, n.Token.Val))
  158. } else {
  159. buf.WriteString(n.Name)
  160. }
  161. if len(n.Meta) > 0 {
  162. buf.WriteString(" # ")
  163. for i, c := range n.Meta {
  164. buf.WriteString(c.Value())
  165. if i < len(n.Meta)-1 {
  166. buf.WriteString(" ")
  167. }
  168. }
  169. }
  170. buf.WriteString("\n")
  171. if printChildren == -1 || printChildren > 0 {
  172. if printChildren != -1 {
  173. printChildren--
  174. }
  175. // Print children
  176. for _, child := range n.Children {
  177. child.levelString(indent+1, buf, printChildren)
  178. }
  179. }
  180. }
  181. /*
  182. ToJSONObject returns this ASTNode and all its children as a JSON object.
  183. */
  184. func (n *ASTNode) ToJSONObject() map[string]interface{} {
  185. ret := make(map[string]interface{})
  186. ret["name"] = n.Name
  187. lenMeta := len(n.Meta)
  188. if lenMeta > 0 {
  189. meta := make([]map[string]interface{}, lenMeta)
  190. for i, metaChild := range n.Meta {
  191. meta[i] = map[string]interface{}{
  192. "type": metaChild.Type(),
  193. "value": metaChild.Value(),
  194. }
  195. }
  196. ret["meta"] = meta
  197. }
  198. lenChildren := len(n.Children)
  199. if lenChildren > 0 {
  200. children := make([]map[string]interface{}, lenChildren)
  201. for i, child := range n.Children {
  202. children[i] = child.ToJSONObject()
  203. }
  204. ret["children"] = children
  205. }
  206. // The value is what the lexer found in the source
  207. if n.Token != nil {
  208. ret["id"] = n.Token.ID
  209. if n.Token.Val != "" {
  210. ret["value"] = n.Token.Val
  211. }
  212. ret["identifier"] = n.Token.Identifier
  213. ret["allowescapes"] = n.Token.AllowEscapes
  214. ret["pos"] = n.Token.Pos
  215. ret["source"] = n.Token.Lsource
  216. ret["line"] = n.Token.Lline
  217. ret["linepos"] = n.Token.Lpos
  218. }
  219. return ret
  220. }
  221. /*
  222. ASTFromJSONObject creates an AST from a JSON Object.
  223. The following nested map structure is expected:
  224. {
  225. name : <name of node>
  226. // Optional node information
  227. value : <value of node>
  228. children : [ <child nodes> ]
  229. // Optional token information
  230. id : <token id>
  231. }
  232. */
  233. func ASTFromJSONObject(jsonAST map[string]interface{}) (*ASTNode, error) {
  234. var astMeta []MetaData
  235. var astChildren []*ASTNode
  236. nodeID := TokenANY
  237. name, ok := jsonAST["name"]
  238. if !ok {
  239. return nil, fmt.Errorf("Found json ast node without a name: %v", jsonAST)
  240. }
  241. if nodeIDString, ok := jsonAST["id"]; ok {
  242. if nodeIDInt, err := strconv.Atoi(fmt.Sprint(nodeIDString)); err == nil && IsValidTokenID(nodeIDInt) {
  243. nodeID = LexTokenID(nodeIDInt)
  244. }
  245. }
  246. getVal := func(k string, d interface{}) (interface{}, int) {
  247. value, ok := jsonAST[k]
  248. if !ok {
  249. value = d
  250. }
  251. numVal, _ := strconv.Atoi(fmt.Sprint(value))
  252. return value, numVal
  253. }
  254. value, _ := getVal("value", "")
  255. identifier, _ := getVal("identifier", false)
  256. allowescapes, _ := getVal("allowescapes", false)
  257. _, pos := getVal("pos", "")
  258. _, line := getVal("line", "")
  259. _, linepos := getVal("linepos", "")
  260. source, _ := getVal("source", "")
  261. // Create meta data
  262. if meta, ok := jsonAST["meta"]; ok {
  263. if ic, ok := meta.([]interface{}); ok {
  264. // Do a list conversion if necessary - this is necessary when we parse
  265. // JSON with map[string]interface{}
  266. metaList := make([]map[string]interface{}, len(ic))
  267. for i := range ic {
  268. metaList[i] = ic[i].(map[string]interface{})
  269. }
  270. meta = metaList
  271. }
  272. for _, metaChild := range meta.([]map[string]interface{}) {
  273. astMeta = append(astMeta, &metaData{
  274. fmt.Sprint(metaChild["type"]), fmt.Sprint(metaChild["value"])})
  275. }
  276. }
  277. // Create children
  278. if children, ok := jsonAST["children"]; ok {
  279. if ic, ok := children.([]interface{}); ok {
  280. // Do a list conversion if necessary - this is necessary when we parse
  281. // JSON with map[string]interface{}
  282. childrenList := make([]map[string]interface{}, len(ic))
  283. for i := range ic {
  284. childrenList[i] = ic[i].(map[string]interface{})
  285. }
  286. children = childrenList
  287. }
  288. for _, child := range children.([]map[string]interface{}) {
  289. astChild, err := ASTFromJSONObject(child)
  290. if err != nil {
  291. return nil, err
  292. }
  293. astChildren = append(astChildren, astChild)
  294. }
  295. }
  296. token := &LexToken{
  297. nodeID, // ID
  298. pos, // Pos
  299. fmt.Sprint(value), // Val
  300. identifier == true, // Identifier
  301. allowescapes == true, // AllowEscapes
  302. fmt.Sprint(source), // Lsource
  303. line, // Lline
  304. linepos, // Lpos
  305. }
  306. return &ASTNode{fmt.Sprint(name), token, astMeta, astChildren, nil, 0, nil, nil}, nil
  307. }
  308. // Look ahead buffer
  309. // =================
  310. /*
  311. LABuffer models a look-ahead buffer.
  312. */
  313. type LABuffer struct {
  314. tokens chan LexToken
  315. buffer *datautil.RingBuffer
  316. }
  317. /*
  318. NewLABuffer creates a new NewLABuffer instance.
  319. */
  320. func NewLABuffer(c chan LexToken, size int) *LABuffer {
  321. if size < 1 {
  322. size = 1
  323. }
  324. ret := &LABuffer{c, datautil.NewRingBuffer(size)}
  325. v, more := <-ret.tokens
  326. ret.buffer.Add(v)
  327. for ret.buffer.Size() < size && more && v.ID != TokenEOF {
  328. v, more = <-ret.tokens
  329. ret.buffer.Add(v)
  330. }
  331. return ret
  332. }
  333. /*
  334. Next returns the next item.
  335. */
  336. func (b *LABuffer) Next() (LexToken, bool) {
  337. ret := b.buffer.Poll()
  338. if v, more := <-b.tokens; more {
  339. b.buffer.Add(v)
  340. }
  341. if ret == nil {
  342. return LexToken{ID: TokenEOF}, false
  343. }
  344. return ret.(LexToken), true
  345. }
  346. /*
  347. Peek looks inside the buffer starting with 0 as the next item.
  348. */
  349. func (b *LABuffer) Peek(pos int) (LexToken, bool) {
  350. if pos >= b.buffer.Size() {
  351. return LexToken{ID: TokenEOF}, false
  352. }
  353. return b.buffer.Get(pos).(LexToken), true
  354. }