traversal.go 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267
  1. /*
  2. * EliasDB
  3. *
  4. * Copyright 2016 Matthias Ladkau. All rights reserved.
  5. *
  6. * This Source Code Form is subject to the terms of the Mozilla Public
  7. * License, v. 2.0. If a copy of the MPL was not distributed with this
  8. * file, You can obtain one at http://mozilla.org/MPL/2.0/.
  9. */
  10. package interpreter
  11. import (
  12. "strings"
  13. "devt.de/krotik/eliasdb/eql/parser"
  14. "devt.de/krotik/eliasdb/graph/data"
  15. )
  16. /*
  17. traversalRuntime is the runtime for traversals.
  18. */
  19. type traversalRuntime struct {
  20. rtp *eqlRuntimeProvider
  21. node *parser.ASTNode
  22. where *parser.ASTNode // Traversal where clause
  23. sourceNode data.Node // Source node for traversal - should be injected by the parent
  24. spec string // Spec for this traversal
  25. specIndex int // Index of this traversal in the traversals array
  26. nodes []data.Node // Nodes of the last traversal result
  27. edges []data.Edge // Edges of the last traversal result
  28. curptr int // Pointer to the next node in the last traversal result
  29. }
  30. /*
  31. traversalRuntimeInst returns a new runtime component instance.
  32. */
  33. func traversalRuntimeInst(rtp *eqlRuntimeProvider, node *parser.ASTNode) parser.Runtime {
  34. return &traversalRuntime{rtp, node, nil, nil, "", -1, nil, nil, 0}
  35. }
  36. /*
  37. Validate this node and all its child nodes.
  38. */
  39. func (rt *traversalRuntime) Validate() error {
  40. spec := rt.node.Children[0].Token.Val
  41. rt.specIndex = -1
  42. // Check traversal spec
  43. sspec := strings.Split(spec, ":")
  44. if len(sspec) != 4 {
  45. return rt.rtp.newRuntimeError(ErrInvalidSpec, spec, rt.node)
  46. }
  47. rt.spec = spec
  48. rt.specIndex = len(rt.rtp.specs)
  49. rt.where = nil
  50. rt.rtp.specs = append(rt.rtp.specs, spec)
  51. rt.rtp.attrsNodes = append(rt.rtp.attrsNodes, make(map[string]string))
  52. rt.rtp.attrsEdges = append(rt.rtp.attrsEdges, make(map[string]string))
  53. // Go through all deeper traversals
  54. for _, child := range rt.node.Children[1:] {
  55. if child.Name == parser.NodeTRAVERSE {
  56. if err := child.Runtime.Validate(); err != nil {
  57. return err
  58. }
  59. } else if child.Name == parser.NodeWHERE {
  60. whereRuntime := child.Runtime.(*whereRuntime)
  61. whereRuntime.specIndex = rt.specIndex
  62. // Reset state of where and store it
  63. if err := whereRuntime.Validate(); err != nil {
  64. return err
  65. }
  66. rt.where = child
  67. } else {
  68. return rt.rtp.newRuntimeError(ErrInvalidConstruct, child.Name, child)
  69. }
  70. }
  71. return nil
  72. }
  73. /*
  74. hasMoreNodes returns true if this traversal runtime component can produce more
  75. nodes. If the result is negative then a new source node is required.
  76. */
  77. func (rt *traversalRuntime) hasMoreNodes() bool {
  78. for _, child := range rt.node.Children[1:] {
  79. if child.Name == parser.NodeTRAVERSE {
  80. childRuntime := child.Runtime.(*traversalRuntime)
  81. if childRuntime.hasMoreNodes() {
  82. return true
  83. }
  84. }
  85. }
  86. return rt.curptr < len(rt.nodes)
  87. }
  88. /*
  89. newSource assigns a new source node to this traversal component and
  90. traverses it.
  91. */
  92. func (rt *traversalRuntime) newSource(node data.Node) error {
  93. var nodes []data.Node
  94. var edges []data.Edge
  95. rt.sourceNode = node
  96. // Do the actual traversal if we got a node
  97. if node != nil {
  98. var err error
  99. // Do a simple traversal without getting any node data first
  100. nodes, edges, err = rt.rtp.gm.TraverseMulti(rt.rtp.part, rt.sourceNode.Key(),
  101. rt.sourceNode.Kind(), rt.spec, false)
  102. if err != nil {
  103. return err
  104. }
  105. // Now get the attributes which are required
  106. for _, node := range nodes {
  107. attrs := rt.rtp._attrsNodesFetch[rt.specIndex]
  108. if len(attrs) > 0 {
  109. n, err := rt.rtp.gm.FetchNodePart(rt.rtp.part, node.Key(), node.Kind(), attrs)
  110. if err != nil {
  111. return err
  112. } else if n != nil {
  113. for _, attr := range attrs {
  114. node.SetAttr(attr, n.Attr(attr))
  115. }
  116. }
  117. }
  118. }
  119. for _, edge := range edges {
  120. attrs := rt.rtp._attrsEdgesFetch[rt.specIndex]
  121. if len(attrs) > 0 {
  122. e, err := rt.rtp.gm.FetchEdgePart(rt.rtp.part, edge.Key(), edge.Kind(), attrs)
  123. if err != nil {
  124. return err
  125. } else if e != nil {
  126. for _, attr := range attrs {
  127. edge.SetAttr(attr, e.Attr(attr))
  128. }
  129. }
  130. }
  131. }
  132. }
  133. // Apply where clause
  134. if rt.where != nil {
  135. fNodes := make([]data.Node, 0, len(nodes))
  136. fEdges := make([]data.Edge, 0, len(edges))
  137. for i, node := range nodes {
  138. edge := edges[i]
  139. res, err := rt.where.Runtime.(CondRuntime).CondEval(node, edge)
  140. if err != nil {
  141. return err
  142. }
  143. if res.(bool) {
  144. fNodes = append(fNodes, node)
  145. fEdges = append(fEdges, edge)
  146. }
  147. }
  148. nodes = fNodes
  149. edges = fEdges
  150. }
  151. rt.nodes = nodes
  152. rt.edges = edges
  153. rt.curptr = 0
  154. // Check if there are no nodes to display and return an error if
  155. // empty traversals are not allowed
  156. if len(rt.nodes) == 0 && !rt.rtp.allowNilTraversal {
  157. return ErrEmptyTraversal
  158. }
  159. // Evaluate the new source
  160. _, err := rt.Eval()
  161. return err
  162. }
  163. /*
  164. Eval evaluate this runtime component.
  165. */
  166. func (rt *traversalRuntime) Eval() (interface{}, error) {
  167. // Check if a child can handle the call
  168. for _, child := range rt.node.Children[1:] {
  169. if child.Name == parser.NodeTRAVERSE {
  170. childRuntime := child.Runtime.(*traversalRuntime)
  171. if childRuntime.hasMoreNodes() {
  172. return childRuntime.Eval()
  173. }
  174. }
  175. }
  176. // Get the next node and fill the row entry in the provider
  177. var rowNode data.Node
  178. var rowEdge data.Edge
  179. if rt.curptr < len(rt.nodes) {
  180. // Get a new node from our node list if possible
  181. rowNode = rt.nodes[rt.curptr]
  182. rowEdge = rt.edges[rt.curptr]
  183. rt.curptr++
  184. }
  185. if len(rt.rtp.rowNode) == rt.specIndex {
  186. rt.rtp.rowNode = append(rt.rtp.rowNode, rowNode)
  187. rt.rtp.rowEdge = append(rt.rtp.rowEdge, rowEdge)
  188. } else {
  189. rt.rtp.rowNode[rt.specIndex] = rowNode
  190. rt.rtp.rowEdge[rt.specIndex] = rowEdge
  191. }
  192. // Give the new source to the children and let them evaluate
  193. for _, child := range rt.node.Children[1:] {
  194. if child.Name == parser.NodeTRAVERSE {
  195. childRuntime := child.Runtime.(*traversalRuntime)
  196. if err := childRuntime.newSource(rt.rtp.rowNode[rt.specIndex]); err != nil {
  197. return nil, err
  198. }
  199. }
  200. }
  201. return nil, nil
  202. }