CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

1
# -*- coding: binary -*-
2

3
module Rex
4
  module Parser
5
    #
6
    # A partial implementation of the GraphML specification for loading structured data from an XML file. Notable
7
    # missing components include GraphML parse meta-data (XML attributes with the "parse" prefix), hyperedges and ports.
8
    # See: http://graphml.graphdrawing.org/
9
    #
10
    module GraphML
11
      #
12
      # Load the contents of a GraphML file by parsing it with Nokogiri and returning
13
      # the top level GraphML structure.
14
      #
15
      # @param file_path [String] The file path to load the data from.
16
      # @return [Rex::Parser::GraphML::Element::GraphML]
17
      def self.from_file(file_path)
18
        parser = Nokogiri::XML::SAX::Parser.new(Document.new)
19
        parser.parse(File.read(file_path, mode: 'rb'))
20
        parser.document.graphml
21
      end
22

23
      #
24
      # Convert a GraphML value string into a Ruby value depending on the specified type. Values of int and long will be
25
      # converted to Ruby integer, while float and double values will be converted to floats. For booleans, values that are
26
      # either blank or "false" (case-insensitive) will evaluate to Ruby's false, while everything else will be true.
27
      #
28
      # @param attr_type [Symbol] The type of the attribute, one of either boolean, int, long, float, double or string.
29
      # @param value [String] The value to convert into a native Ruby data type.
30
      def self.convert_attribute(attr_type, value)
31
        case attr_type
32
        when :boolean
33
          value.strip!
34
          if value.blank?
35
            value = false
36
          else
37
            value = value.downcase != 'false'
38
          end
39
        when :int, :long
40
          value = Integer(value)
41
        when :float, :double
42
          value = Float(value)
43
        when :string # rubocop:disable Lint/EmptyWhen
44
        else
45
          raise ArgumentError, 'Unsupported attribute type: ' + attr_type.to_s
46
        end
47

48
        value
49
      end
50

51
      #
52
      # Define a GraphML attribute including its name, data type, default value and where it can be applied.
53
      #
54
      class MetaAttribute
55
        # @param id [String] The attribute's document identifier.
56
        # @param name [String] The attribute's name as used by applications.
57
        # @param type [Symbol] The data type of the attribute, one of either boolean, int, long, float, double or string.
58
        # @param domain [Symbol] What elements this attribute is valid for, one of either edge, node, graph or all.
59
        # @param default An optional default value for this attribute.
60
        def initialize(id, name, type, domain: :all, default: nil)
61
          @id = id
62
          @name = name
63
          @type = type
64
          @domain = domain
65
          @default = default
66
        end
67

68
        #
69
        # Create a new instance from a Key element.
70
        #
71
        # @param key [Rex::Parser::GraphML::Element::Key] The key to create a new instance from.
72
        def self.from_key(key)
73
          new(key.id, key.attr_name, key.attr_type, domain: key.domain, default: key.default&.value)
74
        end
75

76
        #
77
        # Convert a value to the type specified by this attribute.
78
        #
79
        # @param value The value to convert.
80
        def convert(value)
81
          GraphML.convert_attribute(@type, value)
82
        end
83

84
        #
85
        # Whether or not the attribute is valid for the specified element.
86
        #
87
        # @param element [Rex::Parser::GraphML::AttributeContainer] The element to check.
88
        def valid_for?(element)
89
          @domain == :all || @domain == element.class::ELEMENT_NAME.to_sym
90
        end
91

92
        # @!attribute id
93
        #   @return [String] The attribute's document identifier.
94
        attr_reader :id
95
        # @!attribute name
96
        #   @return [String] The attribute's name as used by applications.
97
        attr_reader :name
98
        # @!attribute type
99
        #   @return [Symbol] The data type of the attribute.
100
        attr_reader :type
101
        # @!attribute domain
102
        #   @return [Symbol] What elements this attribute is valid for.
103
        attr_reader :domain
104
        # @!attribute default
105
        #   @return An optional default value for this attribute.
106
        attr_reader :default
107
      end
108

109
      #
110
      # A base class for GraphML elements that are capable of storing attributes.
111
      #
112
      class AttributeContainer
113
        def initialize
114
          @attributes = {}
115
        end
116

117
        # @!attribute attributes
118
        #   @return [Hash] The defined attributes for the element.
119
        attr_reader :attributes
120
      end
121

122
      #
123
      # A module for organizing GraphML elements that define the data structure. Each provides a from_xml_attributes
124
      # function to create an instance from a hash of XML attributes.
125
      #
126
      module Element
127
        #
128
        # A data element defines the value of an attribute for the parent XML node.
129
        # See: http://graphml.graphdrawing.org/specification/xsd.html#element-data
130
        #
131
        class Data
132
          ELEMENT_NAME = 'data'.freeze
133
          # @param key [String] The identifier of the attribute that this object contains a value for.
134
          def initialize(key)
135
            @key = key
136
            @value = nil
137
          end
138

139
          def self.from_xml_attributes(xml_attrs)
140
            key = xml_attrs['key']
141
            raise Error::InvalidAttributeError.new('data', 'key') if key.nil?
142

143
            new(key)
144
          end
145

146
          # @!attribute key
147
          #   @return [String] The identifier of the attribute that this object contains a value for.
148
          attr_reader :key
149
          # @!attribute value
150
          #   @return The value of the attribute.
151
          attr_reader :value
152
        end
153

154
        #
155
        # A default element defines the optional default value of an attribute. If not default is specified, per the GraphML
156
        # specification, the attribute is undefined.
157
        # See: http://graphml.graphdrawing.org/specification/xsd.html#element-default
158
        #
159
        class Default
160
          ELEMENT_NAME = 'default'.freeze
161
          # @param value The default attribute value.
162
          def initialize(value: nil)
163
            @value = value
164
          end
165

166
          def self.from_xml_attributes(_xml_attrs)
167
            new # no attributes for this element
168
          end
169

170
          # @!attribute value
171
          #   @return The default attribute value.
172
          attr_reader :value
173
        end
174

175
        #
176
        # An edge element defines a connection between two nodes. Connections are optionally directional.
177
        # See: http://graphml.graphdrawing.org/specification/xsd.html#element-edge
178
        #
179
        class Edge < AttributeContainer
180
          ELEMENT_NAME = 'edge'.freeze
181
          # @param source [String] The id of the node that this edge originated from.
182
          # @param target [String] The id of the node that this edge is destined for.
183
          # @param directed [Boolean] Whether or not this edge only connects in one direction.
184
          # @param id [String] The optional, unique identifier of this edge.
185
          def initialize(source, target, directed, id: nil)
186
            @source = source
187
            @target = target
188
            @directed = directed
189
            @id = id
190
            super()
191
          end
192

193
          def self.from_xml_attributes(xml_attrs, edgedefault)
194
            source = xml_attrs['source']
195
            raise Error::InvalidAttributeError.new('edge', 'source') if source.nil?
196

197
            target = xml_attrs['target']
198
            raise Error::InvalidAttributeError.new('edge', 'target') if target.nil?
199

200
            directed = xml_attrs['directed']
201
            if directed.nil?
202
              directed = edgedefault == :directed
203
            elsif %w[true false].include? directed
204
              directed = directed == 'true'
205
            else
206
              raise Error::InvalidAttributeError.new('edge', 'directed', details: 'must be either true or false when specified', missing: false)
207
            end
208

209
            new(source, target, directed, id: xml_attrs['id'])
210
          end
211

212
          # !@attribute source
213
          #   @return [String] The id of the node that this edge originated from.
214
          attr_reader :source
215
          # !@attribute target
216
          #   @return [String] The id of the node that this edge is destined for.
217
          attr_reader :target
218
          # !@attribute directed
219
          #   @return [Boolean] Whether or not this edge only connects in one direction.
220
          attr_reader :directed
221
          # !@attribute id
222
          #   @return [String] The optional, unique identifier of this edge.
223
          attr_reader :id
224
        end
225

226
        #
227
        # A graph element defines a collection of nodes and edges.
228
        # See: http://graphml.graphdrawing.org/specification/xsd.html#element-graph
229
        #
230
        class Graph < AttributeContainer
231
          ELEMENT_NAME = 'graph'.freeze
232
          # @param edgedefault [Boolean] Whether or not edges within this graph should be directional by default.
233
          # @param id [String] The optional, unique identifier of this graph.
234
          def initialize(edgedefault, id: nil)
235
            @edgedefault = edgedefault
236
            @id = id
237

238
            @nodes = {}
239
            @edges = []
240
            super()
241
          end
242

243
          def self.from_xml_attributes(xml_attrs)
244
            edgedefault = xml_attrs['edgedefault']
245
            unless %w[directed undirected].include? edgedefault
246
              # see: http://graphml.graphdrawing.org/primer/graphml-primer.html section 2.3.1
247
              raise Error::InvalidAttributeError.new('graph', 'edgedefault', missing: edgedefault.nil?)
248
            end
249

250
            edgedefault = edgedefault.to_sym
251

252
            new(edgedefault, id: xml_attrs['id'])
253
          end
254

255
          # @!attribute edgedefault
256
          #   @return [Boolean] Whether or not edges within this graph should be directional by default.
257
          attr_reader :edgedefault
258
          # @!attribute id
259
          #   @return [String] The optional, unique identifier of this graph.
260
          attr_reader :id
261
          # @!attribute edges
262
          #   @return [Array] An array of edge elements within this graph.
263
          attr_reader :edges
264
          # @!attribute nodes
265
          #   @return [Hash] A hash of node elements, keyed by their string identifier.
266
          attr_reader :nodes
267
        end
268

269
        #
270
        # A graphml element is the root of a GraphML document.
271
        # See: http://graphml.graphdrawing.org/specification/xsd.html#element-graphml
272
        #
273
        class GraphML
274
          ELEMENT_NAME = 'graphml'.freeze
275
          def initialize
276
            @nodes = {}
277
            @edges = []
278
            @graphs = []
279
          end
280

281
          # @!attribute nodes
282
          #   @return [Hash] A hash of all node elements within this GraphML document, keyed by their string identifier.
283
          attr_reader :nodes
284
          # @!attribute edges
285
          #   @return [Array] An array of all edge elements within this GraphML document.
286
          attr_reader :edges
287
          # @!attribute graphs
288
          #   @return [Array] An array of all graph elements within this GraphML document.
289
          attr_reader :graphs
290
        end
291

292
        #
293
        # A key element defines the attributes that may be present in a document.
294
        # See: http://graphml.graphdrawing.org/specification/xsd.html#element-key
295
        #
296
        class Key
297
          ELEMENT_NAME = 'key'.freeze
298
          # @param id [String] The document identifier of the attribute described by this element.
299
          # @param name [String] The name (as used by applications) of the attribute described by this element.
300
          # @param type [Symbol] The data type of the attribute described by this element, one of either boolean, int, long, float, double or string.
301
          # @param domain [Symbol] What elements the attribute described by this element is valid for, one of either edge, node, graph or all.
302
          def initialize(id, name, type, domain)
303
            @id = id
304
            @attr_name = name
305
            @attr_type = type
306
            @domain = domain # using 'for' would cause an awkward keyword conflict
307
            @default = nil
308
          end
309

310
          def self.from_xml_attributes(xml_attrs)
311
            id = xml_attrs['id']
312
            raise Error::InvalidAttributeError.new('key', 'id') if id.nil?
313

314
            name = xml_attrs['attr.name']
315
            raise Error::InvalidAttributeError.new('key', 'attr.name') if name.nil?
316

317
            type = xml_attrs['attr.type']
318
            unless %w[boolean int long float double string].include? type
319
              raise Error::InvalidAttributeError.new('key', 'attr.type', details: 'must be boolean int long float double or string', missing: type.nil?)
320
            end
321

322
            type = type.to_sym
323

324
            domain = xml_attrs['for']
325
            unless %w[graph node edge all].include? domain
326
              raise Error::InvalidAttributeError.new('key', 'for', details: 'must be graph node edge or all', missing: domain.nil?)
327
            end
328

329
            domain = domain.to_sym
330

331
            new(id, name, type, domain)
332
          end
333

334
          def default=(value)
335
            @default = GraphML.convert_attribute(@attr_type, value)
336
          end
337

338
          # @!attribute id
339
          #   @return [String] The document identifier of the attribute described by this element.
340
          attr_reader :id
341
          # @!attribute attr_name
342
          #   @return [String] The name (as used by applications) of the attribute described by this element.
343
          attr_reader :attr_name
344
          # @!attribute attr_type
345
          #   @return [Symbol] The data type of the attribute described by this element.
346
          attr_reader :attr_type
347
          # @!attribute domain
348
          #   @return [Symbol] What elements the attribute described by this element is valid for.
349
          attr_reader :domain
350
          # @!attribute default
351
          #   @return The default value of the attribute described by this element.
352
          attr_reader :default
353
        end
354

355
        #
356
        # A node element defines an object within the graph that can have zero or more edges connecting it to other nodes. A
357
        # node element may contain a graph element.
358
        #
359
        class Node < AttributeContainer
360
          ELEMENT_NAME = 'node'.freeze
361
          # @param id [String] The unique identifier for this node element.
362
          def initialize(id)
363
            @id = id
364
            @edges = []
365
            @subgraph = nil
366
            super()
367
          end
368

369
          def self.from_xml_attributes(xml_attrs)
370
            id = xml_attrs['id']
371
            raise Error::InvalidAttributeError.new('node', 'id') if id.nil?
372

373
            new(id)
374
          end
375

376
          # @return [Array] An array of all edges for which this node is the target.
377
          def source_edges
378
            # edges connected to this node
379
            @edges.select { |edge| edge.target == @id || !edge.directed }
380
          end
381

382
          # @return [Array] An array of all edges for which this node is the source.
383
          def target_edges
384
            # edges connecting this to other nodes
385
            @edges.select { |edge| edge.source == @id || !edge.directed }
386
          end
387

388
          # @!attribute id
389
          #   @return [String] The unique identifier for this node.
390
          attr_reader :id
391
          # @!attribute edges
392
          #   @return [Array] An array of all edges for which this node is either the source or the target.
393
          attr_reader :edges
394
          # @!attribute subgraph
395
          #   @return [Graph,nil] A subgraph contained within this node.
396
          attr_accessor :subgraph
397
        end
398
      end
399

400
      #
401
      # A module collecting the errors raised by this parser.
402
      #
403
      module Error
404
        #
405
        # The base error class for errors raised by this parser.
406
        #
407
        class GraphMLError < StandardError
408
        end
409

410
        #
411
        # An error describing an issue that occurred while parsing the data structure.
412
        #
413
        class ParserError < GraphMLError
414
        end
415

416
        #
417
        # An error describing an XML attribute that is invalid either because the value is missing or otherwise invalid.
418
        #
419
        class InvalidAttributeError < ParserError
420
          def initialize(element, attribute, details: nil, missing: true)
421
            @element = element
422
            @attribute = attribute
423
            # whether or not the attribute is invalid because it is absent
424
            @missing = missing
425

426
            message = "Element '#{element}' contains an invalid attribute: '#{attribute}'"
427
            message << " (#{details})" unless details.nil?
428

429
            super(message)
430
          end
431
        end
432
      end
433

434
      #
435
      # The top-level document parser.
436
      #
437
      class Document < Nokogiri::XML::SAX::Document
438
        def initialize
439
          @stack = []
440
          @nodes = {}
441
          @meta_attributes = {}
442
          @graphml = nil
443
          super
444
        end
445

446
        def start_element(name, attrs = [])
447
          attrs = attrs.to_h
448

449
          case name
450
          when 'data'
451
            raise Error::ParserError, 'The \'data\' element must be a direct child of an attribute container' unless @stack[-1].is_a? AttributeContainer
452

453
            element = Element::Data.from_xml_attributes(attrs)
454

455
          when 'default'
456
            raise Error::ParserError, 'The \'default\' element must be a direct child of a \'key\' element' unless @stack[-1].is_a? Element::Key
457

458
            element = Element::Default.from_xml_attributes(attrs)
459

460
          when 'edge'
461
            raise Error::ParserError, 'The \'edge\' element must be a direct child of a \'graph\' element' unless @stack[-1].is_a? Element::Graph
462

463
            element = Element::Edge.from_xml_attributes(attrs, @stack[-1].edgedefault)
464
            @graphml.edges << element
465

466
          when 'graph'
467
            element = Element::Graph.from_xml_attributes(attrs)
468
            @stack[-1].subgraph = element if @stack[-1].is_a? Element::Node
469
            @graphml.graphs << element
470

471
          when 'graphml'
472
            element = Element::GraphML.new
473
            raise Error::ParserError, 'The \'graphml\' element must be a top-level element' unless @stack.empty?
474

475
            @graphml = element
476

477
          when 'key'
478
            raise Error::ParserError, 'The \'key\' element must be a direct child of a \'graphml\' element' unless @stack[-1].is_a? Element::GraphML
479

480
            element = Element::Key.from_xml_attributes(attrs)
481
            raise Error::InvalidAttributeError.new('key', 'id', details: 'duplicate key id') if @meta_attributes.key? element.id
482
            if @meta_attributes.values.any? { |attr| attr.name == element.attr_name }
483
              raise Error::InvalidAttributeError.new('key', 'attr.name', details: 'duplicate key attr.name')
484
            end
485

486
          when 'node'
487
            raise Error::ParserError, 'The \'node\' element must be a direct child of a \'graph\' element' unless @stack[-1].is_a? Element::Graph
488

489
            element = Element::Node.from_xml_attributes(attrs)
490
            raise Error::InvalidAttributeError.new('node', 'id', details: 'duplicate node id') if @nodes.key? element.id
491

492
            @nodes[element.id] = element
493
            @graphml.nodes[element.id] = element
494

495
          else
496
            raise Error::ParserError, 'Unknown element: ' + name
497

498
          end
499

500
          @stack.push element
501
        end
502

503
        def characters(string)
504
          element = @stack[-1]
505
          case element
506
          when Element::Data
507
            parent = @stack[-2]
508
            meta_attribute = @meta_attributes[element.key]
509
            unless meta_attribute.valid_for? parent
510
              raise Error::ParserError, "The #{meta_attribute.name} attribute is invalid for #{parent.class::ELEMENT_NAME} elements"
511
            end
512

513
            if meta_attribute.type == :string && !parent.attributes[meta_attribute.name].nil?
514
              # this may be run multiple times if there is an XML escape sequence in the string to concat the parts together
515
              parent.attributes[meta_attribute.name] << meta_attribute.convert(string)
516
            else
517
              parent.attributes[meta_attribute.name] = meta_attribute.convert(string)
518
            end
519

520
          when Element::Default
521
            @stack[-1] = Element::Default.new(value: string)
522

523
          end
524
        end
525

526
        def end_element(name)
527
          element = @stack.pop
528

529
          populate_element_default_attributes(element) if element.is_a? AttributeContainer
530

531
          case name
532
          when 'default'
533
            key = @stack[-1]
534
            key.default = element
535

536
          when 'edge'
537
            graph = @stack[-1]
538
            graph.edges << element
539

540
          when 'graph'
541
            element.edges.each do |edge|
542
              source_node = element.nodes[edge.source]
543
              raise Error::InvalidAttributeError.new('edge', 'source', details: "undefined source: '#{edge.source}'", missing: false) if source_node.nil?
544

545
              target_node = element.nodes[edge.target]
546
              raise Error::InvalidAttributeError.new('edge', 'target', details: "undefined target: '#{edge.target}'", missing: false) if target_node.nil?
547

548
              source_node.edges << edge
549
              target_node.edges << edge
550
            end
551

552
          when 'key'
553
            meta_attribute = MetaAttribute.from_key(element)
554
            @meta_attributes[meta_attribute.id] = meta_attribute
555

556
          when 'node'
557
            graph = @stack[-1]
558
            graph.nodes[element.id] = element
559

560
          end
561
        end
562

563
        # @!attribute graphml
564
        #   @return [Rex::Parser::GraphML::Element::GraphML] The root of the parsed document.
565
        attr_reader :graphml
566

567
        private
568

569
        def populate_element_default_attributes(element)
570
          @meta_attributes.values.each do |meta_attribute|
571
            next unless meta_attribute.valid_for? element
572
            next if element.attributes.key? meta_attribute.name
573
            next if meta_attribute.default.nil?
574

575
            element.attributes[meta_attribute.name] = meta_attribute.default
576
          end
577
        end
578
      end
579
    end
580
  end
581
end
582

583