helper.go 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469
  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. var pos, line, linepos int
  237. nodeID := TokenANY
  238. name, ok := jsonAST["name"]
  239. if !ok {
  240. return nil, fmt.Errorf("Found json ast node without a name: %v", jsonAST)
  241. }
  242. if nodeIDString, ok := jsonAST["id"]; ok {
  243. if nodeIDInt, err := strconv.Atoi(fmt.Sprint(nodeIDString)); err == nil && IsValidTokenID(nodeIDInt) {
  244. nodeID = LexTokenID(nodeIDInt)
  245. }
  246. }
  247. value, ok := jsonAST["value"]
  248. if !ok {
  249. value = ""
  250. }
  251. identifier, ok := jsonAST["identifier"]
  252. if !ok {
  253. identifier = false
  254. }
  255. allowescapes, ok := jsonAST["allowescapes"]
  256. if !ok {
  257. allowescapes = false
  258. }
  259. if posString, ok := jsonAST["pos"]; ok {
  260. pos, _ = strconv.Atoi(fmt.Sprint(posString))
  261. } else {
  262. pos = 0
  263. }
  264. if lineString, ok := jsonAST["line"]; ok {
  265. line, _ = strconv.Atoi(fmt.Sprint(lineString))
  266. } else {
  267. line = 0
  268. }
  269. if lineposString, ok := jsonAST["linepos"]; ok {
  270. linepos, _ = strconv.Atoi(fmt.Sprint(lineposString))
  271. } else {
  272. linepos = 0
  273. }
  274. source, ok := jsonAST["source"]
  275. if !ok {
  276. source = ""
  277. }
  278. // Create meta data
  279. if meta, ok := jsonAST["meta"]; ok {
  280. if ic, ok := meta.([]interface{}); ok {
  281. // Do a list conversion if necessary - this is necessary when we parse
  282. // JSON with map[string]interface{}
  283. metaList := make([]map[string]interface{}, len(ic))
  284. for i := range ic {
  285. metaList[i] = ic[i].(map[string]interface{})
  286. }
  287. meta = metaList
  288. }
  289. for _, metaChild := range meta.([]map[string]interface{}) {
  290. astMeta = append(astMeta, &metaData{
  291. fmt.Sprint(metaChild["type"]), fmt.Sprint(metaChild["value"])})
  292. }
  293. }
  294. // Create children
  295. if children, ok := jsonAST["children"]; ok {
  296. if ic, ok := children.([]interface{}); ok {
  297. // Do a list conversion if necessary - this is necessary when we parse
  298. // JSON with map[string]interface{}
  299. childrenList := make([]map[string]interface{}, len(ic))
  300. for i := range ic {
  301. childrenList[i] = ic[i].(map[string]interface{})
  302. }
  303. children = childrenList
  304. }
  305. for _, child := range children.([]map[string]interface{}) {
  306. astChild, err := ASTFromJSONObject(child)
  307. if err != nil {
  308. return nil, err
  309. }
  310. astChildren = append(astChildren, astChild)
  311. }
  312. }
  313. token := &LexToken{
  314. nodeID, // ID
  315. pos, // Pos
  316. fmt.Sprint(value), // Val
  317. identifier == true, // Identifier
  318. allowescapes == true, // AllowEscapes
  319. fmt.Sprint(source), // Lsource
  320. line, // Lline
  321. linepos, // Lpos
  322. }
  323. return &ASTNode{fmt.Sprint(name), token, astMeta, astChildren, nil, 0, nil, nil}, nil
  324. }
  325. // Look ahead buffer
  326. // =================
  327. /*
  328. LABuffer models a look-ahead buffer.
  329. */
  330. type LABuffer struct {
  331. tokens chan LexToken
  332. buffer *datautil.RingBuffer
  333. }
  334. /*
  335. NewLABuffer creates a new NewLABuffer instance.
  336. */
  337. func NewLABuffer(c chan LexToken, size int) *LABuffer {
  338. if size < 1 {
  339. size = 1
  340. }
  341. ret := &LABuffer{c, datautil.NewRingBuffer(size)}
  342. v, more := <-ret.tokens
  343. ret.buffer.Add(v)
  344. for ret.buffer.Size() < size && more && v.ID != TokenEOF {
  345. v, more = <-ret.tokens
  346. ret.buffer.Add(v)
  347. }
  348. return ret
  349. }
  350. /*
  351. Next returns the next item.
  352. */
  353. func (b *LABuffer) Next() (LexToken, bool) {
  354. ret := b.buffer.Poll()
  355. if v, more := <-b.tokens; more {
  356. b.buffer.Add(v)
  357. }
  358. if ret == nil {
  359. return LexToken{ID: TokenEOF}, false
  360. }
  361. return ret.(LexToken), true
  362. }
  363. /*
  364. Peek looks inside the buffer starting with 0 as the next item.
  365. */
  366. func (b *LABuffer) Peek(pos int) (LexToken, bool) {
  367. if pos >= b.buffer.Size() {
  368. return LexToken{ID: TokenEOF}, false
  369. }
  370. return b.buffer.Get(pos).(LexToken), true
  371. }