developer.intra2net.com Git - pyi2ncommon/blob - src/cnfvar/string.py

   1 #!/usr/bin/env python
   2 #
   3 # The software in this package is distributed under the GNU General
   4 # Public License version 2 (with a special exception described below).
   5 #
   6 # A copy of GNU General Public License (GPL) is included in this distribution,
   7 # in the file COPYING.GPL.
   8 #
   9 # As a special exception, if other files instantiate templates or use macros
  10 # or inline functions from this file, or you compile this file and link it
  11 # with other works to produce a work based on this file, this file
  12 # does not by itself cause the resulting work to be covered
  13 # by the GNU General Public License.
  14 #
  15 # However the source code for this file must still be made available
  16 # in accordance with section (3) of the GNU General Public License.
  17 #
  18 # This exception does not invalidate any other reasons why a work based
  19 # on this file might be covered by the GNU General Public License.
  20 #
  21 # Copyright (c) 2016-2018 Intra2net AG <info@intra2net.com>
  22
  23 """
  24 string: functionality for parsing cnfvars from strings
  25
  26 .. codeauthor:: Intra2net
  27
  28
  29 contents
  30 -------------------------------------------------------------------------------
  31
  32 This module provides read and parse functionality for the Intra2net *CNF*
  33 format from strings and by extension cnf files.
  34
  35 The input string takes one round-trip through the parsers and will error out on
  36 problematic lines. Thus, this module can also be used to syntax-check CNF data.
  37
  38 Note that line numbers may be arbitrarily reassigned in the process. Of course,
  39 parent references and the relative ordering of lines will be preserved in this
  40 case.
  41
  42 .. todo::
  43     Decide on some facility for automatic fixup of line number values. The
  44     internal representation is recursive so line numbers are not needed to
  45     establish a variable hierarchy. They might as well be omitted from the json
  46     input and only added when writing cnf. For the time being a lack of the
  47     "number" field is interpreted as an error. Though it should at least
  48     optionally be possible to omit the numbers entirely and have a function add
  49     them after the fact. This might as well be added to :py:func:`is_cnf`
  50     though it would be counterintuitive to have a predicate mutate its
  51     argument. So maybe it could return a second argument to indicate a valid
  52     structure that needs fixup or something like that.
  53
  54 .. note::
  55     The variable values of get_cnf seems to be encoded in latin1, and set_cnf
  56     seems to assume latin1-encoded values (not var names). Function
  57     :py:func:`read_cnf` converts this to unicode and other functions convert
  58     unicode back to latin1.
  59
  60
  61 notes on Python 3 conversion
  62 -------------------------------------------------------------------------------
  63
  64 Since the original *CNF* format assumes latin-1 encoded data pretty much
  65 exclusively, we preserve the original encoding while parsing the file.
  66 When assembling the data structures returned to the user, values are then
  67 converted to strings so they can be used naturally at the Python end.
  68
  69 implementation
  70 -------------------------------------------------------------------------------
  71 """
  72
  73 import functools
  74 import sys
  75 import json
  76 import re
  77 import io
  78
  79
  80 ###############################################################################
  81 # CONSTANTS
  82 ###############################################################################
  83
  84
  85 CNF_FIELD_MANDATORY = set ([ "varname", "data", "instance" ])
  86 CNF_FIELD_OPTIONAL  = set ([ "parent", "children", "comment", "number" ])
  87 CNF_FIELD_KNOWN     = CNF_FIELD_MANDATORY | CNF_FIELD_OPTIONAL
  88
  89 grab_parent_pattern = re.compile(b"""
  90                                     ^            # match from start
  91                                     \s*          # optional spaces
  92                                     \d+          # line number
  93                                     \s+          # spaces
  94                                     \((\d+)\)    # parent
  95                                  """,
  96                                  re.VERBOSE)
  97
  98 base_line_pattern = re.compile(b"""
  99                                     ^                    # match from start
 100                                     \s*                  # optional spaces
 101                                     (\d+)                # line number
 102                                     \s+                  # spaces
 103                                     ([A-Z][A-Z0-9_]*)    # varname
 104                                     \s*                  # optional spaces
 105                                     ,                    # delimiter
 106                                     \s*                  # optional spaces
 107                                     (-1|\d+)             # instance
 108                                     \s*                  # optional spaces
 109                                     :                    # delimiter
 110                                     \s*                  # optional spaces
 111                                     \"(                  # quoted string (data)
 112                                        (?:  \\\"         #  (of escaped dquote
 113                                            |[^\"])*      #   or anything not a
 114                                       )\"                #   literal quote)
 115                                     \s*                  # optional spaces
 116                                     (                    # bgroup
 117                                      \#                  # comment leader
 118                                      \s*                 # optional spaces
 119                                      .*                  # string (comment)
 120                                     )?                   # egroup, optional
 121                                     $                    # eol
 122                                """,
 123                                re.VERBOSE)
 124
 125 child_line_pattern = re.compile(b"""
 126                                      ^                    # match from start
 127                                      \s*                  # optional spaces
 128                                      (\d+)                # line number
 129                                      \s+                  # spaces
 130                                      \((\d+)\)            # parent
 131                                      \s+                  # spaces
 132                                      ([A-Z][A-Z0-9_]*)    # varname
 133                                      \s*                  # optional spaces
 134                                      ,                    # delimiter
 135                                      \s*                  # optional spaces
 136                                      (-1|\d+)             # instance
 137                                      \s*                  # optional spaces
 138                                      :                    # delimiter
 139                                      \s*                  # optional spaces
 140                                      \"([^\"]*)\"         # quoted string (data)
 141                                      \s*                  # optional spaces
 142                                      (                    # bgroup
 143                                       \#                  # comment leader
 144                                       \s*                 # optional spaces
 145                                       .*                  # string (comment)
 146                                      )?                   # egroup, optional
 147                                      $                    # eol
 148                                 """,
 149                                 re.VERBOSE)
 150
 151
 152 ###############################################################################
 153 # HELPERS
 154 ###############################################################################
 155
 156
 157 #
 158 # Sadly, the Intranator is still stuck with one leg in the 90s.
 159 #
 160 def to_latin1(s):
 161     """Take given unicode str and convert it to a latin1-encoded `bytes`."""
 162     return s.encode("latin-1")
 163
 164
 165 def from_latin1(s):
 166     """Take given latin1-encoded `bytes` value and convert it to `str`."""
 167     return s.decode("latin-1")
 168
 169
 170 #
 171 # Conversion functions
 172 #
 173
 174 def marshal_in_number(number):
 175     return int(number)
 176
 177
 178 def marshal_in_parent(parent):
 179     return int(parent)
 180
 181
 182 def marshal_in_instance(instance):
 183     return int(instance)
 184
 185
 186 def marshal_in_varname(varname):
 187     return from_latin1(varname).lower()
 188
 189
 190 def marshal_in_data(data):
 191     return from_latin1(data) if data is not None else ""
 192
 193
 194 def marshal_in_comment(comment):
 195     return comment and from_latin1(comment[1:].strip()) or None
 196
 197
 198 #
 199 # Type checking
 200 #
 201
 202 def is_string(s):
 203     return isinstance(s, str)
 204
 205
 206 ###############################################################################
 207 # EXCEPTIONS
 208 ###############################################################################
 209
 210
 211 class InvalidCNF(Exception):
 212
 213     def __init__(self, msg):
 214         self.msg = msg
 215
 216     def __str__(self):
 217         return "Malformed CNF_VAR: \"%s\"" % self.msg
 218
 219
 220 class MalformedCNF(Exception):
 221
 222     def __init__(self, msg):
 223         self.msg = msg
 224
 225     def __str__(self):
 226         return "Malformed CNF file: \"%s\"" % self.msg
 227
 228
 229 ###############################################################################
 230 # VALIDATION
 231 ###############################################################################
 232
 233
 234 def is_valid(acc,
 235              nested,
 236              comment,
 237              data,
 238              instance,
 239              number,
 240              parent,
 241              varname):
 242     if varname is None:
 243         raise InvalidCNF("CNF_VAR lacks a name.")
 244     elif not is_string(varname):
 245         raise InvalidCNF("Varname field of CNF_VAR \"%s\" is not a string."
 246                          % varname)
 247     elif varname == "":
 248         raise InvalidCNF("Varname field of CNF_VAR is the empty string.")
 249
 250     if comment is not None:
 251         if not is_string(comment):
 252             raise InvalidCNF("Comment field of CNF_VAR \"%s\" is not a string."
 253                              % varname)
 254
 255     if data is None:
 256         raise InvalidCNF("Data field of CNF_VAR \"%s\" is empty."
 257                          % varname)
 258     elif not is_string(data):
 259         raise InvalidCNF("Data field of CNF_VAR \"%s\" is not a string."
 260                          % varname)
 261
 262     if instance is None:
 263         raise InvalidCNF("Instance field of CNF_VAR \"%s\" is empty."
 264                          % varname)
 265     elif not isinstance(instance, int):
 266         raise InvalidCNF("Instance field of CNF_VAR \"%s\" is not an integer."
 267                          % varname)
 268
 269     if number is None:
 270         raise InvalidCNF("Number field of CNF_VAR \"%s\" is empty."
 271                          % varname)
 272     elif not isinstance(number, int):
 273         raise InvalidCNF("Number field of CNF_VAR \"%s\" is not an integer."
 274                          % varname)
 275     elif number < 1:
 276         raise InvalidCNF("Number field of CNF_VAR \"%s\" must be positive, not %d."
 277                          % (varname, number))
 278     else:
 279         other = acc.get(number, None)
 280         if other is not None:  # already in use
 281             raise InvalidCNF("Number field of CNF_VAR \"%s\" already used by variable %s."
 282                              % (varname, other))
 283         acc[number] = varname
 284
 285     if nested is True:
 286         if parent is None:
 287             raise InvalidCNF("Parent field of nested CNF_VAR \"%s\" is empty."
 288                              % varname)
 289         elif not isinstance(parent, int):
 290             raise InvalidCNF("Parent field of CNF_VAR \"%s\" is not an integer."
 291                              % varname)
 292     else:
 293         if parent is not None:
 294             raise InvalidCNF("Flat CNF_VAR \"%s\" has nonsensical parent field \"%s\"."
 295                              % (varname, parent))
 296     return acc
 297
 298
 299 def is_cnf(root):
 300     """
 301     is_cnf -- Predicate testing "CNF_VAR-ness". Folds the :py:func:`is_valid`
 302     predicate over the argument which can be either a well-formed CNF
 303     dictionary or a list of CNF_VARs.
 304
 305     :type root: cnfvar or cnf list
 306     :rtype: bool
 307
 308     Not that if it returns at all, ``is_cnf()`` returns ``True``. Any non
 309     well-formed member of the argument will cause the predicate to bail out
 310     with an exception during traversal.
 311     """
 312     cnf = cnf_root(root)
 313     if cnf is None:
 314         raise InvalidCNF(root)
 315     return walk_cnf(cnf, False, is_valid, {}) is not None
 316
 317
 318 def is_cnf_var(obj):
 319     """
 320     Check whether a dictionary is a valid CNF.
 321
 322     :param dict obj: dictionary to check
 323     :returns: True if the dictionary has all the mandatory fields and no
 324               unknown fields, False otherwise
 325     :rtype: bool
 326     """
 327     assert isinstance (obj, dict)
 328
 329     for f in CNF_FIELD_MANDATORY:
 330         if obj.get(f, None) is None:
 331             return False
 332
 333     for f in obj:
 334         if f not in CNF_FIELD_KNOWN:
 335             return False
 336
 337     return True
 338
 339
 340 ###############################################################################
 341 # DESERIALIZATION
 342 ###############################################################################
 343 #
 344 # CNF reader
 345 #
 346 # Parsing usually starts from the `read_cnf`, which accepts a string containing
 347 # the variables to parse in the same structure as returned by `get_cnf`.
 348 #
 349 # In the `prepare` function the string is split into lines, and a 3-element
 350 # tuple is built. The first (named `current`) and second (named `next`)
 351 # elements of this tuple are respectively the first and second non-empty lines
 352 # of the input, while the third is a list of the remaining lines. This tuple is
 353 # named `state` in the implementation below, and it is passed around during
 354 # parsing. The `get` and `peek` functions are used to easily retrieve the
 355 # `current` and `next` items from the "state".
 356 #
 357 # When we "advance" the state, we actually drop the "current" element,
 358 # replacing it with the "next", while a new "next" is popped from the list of
 359 # remaining lines. Parsing is done this way because we need to look ahead at
 360 # the next line -- if it is a child it needs to be appended to the `children`
 361 # property of the current line.
 362 #
 363 # Regular expressions are used to extract important information from the CNF
 364 # lines. Finally, once parsing is completed, a dictionary is returned. The dict
 365 # has the same structure as the serialized JSON output returned by
 366 # `get_cnf -j`.
 367 #
 368
 369
 370 def read_cnf(data):
 371     """
 372     Read cnf data from data bytes.
 373
 374     :param data: raw data
 375     :type data: str or bytes
 376     :return: the parsed cnf data
 377     :rtype: {str, {str, str or int}}
 378     """
 379     if isinstance(data, str):
 380         data = to_latin1(data)
 381     state = prepare(data)
 382     if state is None:
 383         raise InvalidCNF("Empty input string.")
 384
 385     cnf = parse_cnf_root(state)
 386     if is_cnf(cnf) is False:
 387         raise TypeError("Invalid CNF_VAR.")
 388     return {"cnf": cnf}
 389
 390
 391 def prepare(raw):
 392     """
 393     Build 3-element iterable from a CNF string dump.
 394
 395     :param raw: string content as returned by `get_cnf`
 396     :type raw: bytes
 397     :returns: 3-element tuple, where the first two elements are the first two
 398               lines of the output and the third is a list containing the rest
 399               of the lines in reverse.
 400     :rtype: (str * str option * str list) option
 401     """
 402     lines = raw.splitlines()
 403     lines.reverse()
 404     try:
 405         first = lines.pop()
 406     except IndexError:
 407         return None
 408
 409     try:
 410         second = lines.pop()
 411     except IndexError:
 412         second = None
 413
 414     first = first.strip()
 415     if first == b"":
 416         return advance((first, second, lines))
 417
 418     return (first, second, lines)
 419
 420
 421 def advance(cns):
 422     """
 423     Pop the next line from the stream, advancing the tuple.
 424
 425     :param cns: a 3-element tuple containing two CNF lines and a list of the
 426                 remaining lines
 427     :type cnd: (str, str, [str])
 428     :returns: a new tuple with a new item popped from the list of lines
 429     :rtype cnd: (str, str, [str])
 430     """
 431     current, next, stream = cns
 432     if next is None:  # reached end of stream
 433         return None
 434     current = next
 435
 436     try:
 437         next = stream.pop()
 438         next = next.strip()
 439     except IndexError:
 440         next = None
 441
 442     if current == "":  # skip blank lines
 443         return advance((current, next, stream))
 444     return (current, next, stream)
 445
 446
 447 def get(cns):
 448     """
 449     Get the current line from the state without advancing it.
 450
 451     :param cns: a 3-element tuple containing two CNF lines and a list of the
 452                 remaining lines
 453     :type cnd: (str, str, [str])
 454     :returns: the CNF line stored as `current`
 455     :rtype: str
 456     """
 457     current, _, _ = cns
 458     return current
 459
 460
 461 def parse_cnf_root(state):
 462     """
 463     Iterate over and parse a list of CNF lines.
 464
 465     :param state: a 3-element tuple containing two lines and a list of the
 466                   remaining lines
 467     :type state: (str, str, [str])
 468     :returns: a list of parsed CNF variables
 469     :rtype: [dict]
 470
 471     The function will parse the first element from the `state` tuple, then read
 472     the next line to see if it is a child variable. If it is, it will be
 473     appended to the last parsed CNF, otherwise top-level parsing is done
 474     normally.
 475     """
 476     lines = []
 477     current = get(state)
 478     while state:
 479         cnf_line = read_base_line(current)
 480         if cnf_line is not None:
 481             lines.append(cnf_line)
 482             state = advance(state)
 483             if state is None:  # -> nothing left to do
 484                 break
 485             current = get(state)
 486             parent = get_parent(current)  # peek at next line
 487             if parent is not None:  # -> recurse into children
 488                 (state, children, _parent) = parse_cnf_children(state, parent)
 489                 cnf_line["children"] = children
 490                 if state is None:
 491                     break
 492                 current = get(state)
 493         else:
 494             state = advance(state)
 495             if state is None:
 496                 break
 497             current = get(state)
 498     return lines
 499
 500
 501 def parse_cnf_children(state, parent):
 502     """
 503     Read and parse child CNFs of a given parent until there is none left.
 504
 505     :param state: a 3-element tuple containing two lines and a list of the
 506                   remaining lines
 507     :type state: (str, str, [str])
 508     :param parent: id of the parent whose children we are looking for
 509     :type parent: int
 510     :returns: a 3-element tuple with the current state, a list of children of
 511               the given parent and the parent ID
 512     :rtype: (tuple, [str], int)
 513
 514     The function will recursively parse child lines from the `state` tuple
 515     until one of these conditions is satisfied:
 516
 517     1. the input is exhausted
 518     2. the next CNF line
 519         2.1. is a toplevel line
 520         2.2. is a child line whose parent has a lower parent number
 521
 522     Conceptually, 2.1 is a very similar to 2.2 but due to the special status of
 523     toplevel lines in CNF we need to handle them separately.
 524
 525     Note that since nesting of CNF vars is achieved via parent line numbers,
 526     lines with different parents could appear out of order. libcnffile will
 527     happily parse those and still assign children to the specified parent:
 528
 529     ::
 530         # set_cnf <<THATSALL
 531         1 USER,1337: "l33t_h4x0r"
 532         2    (1) USER_GROUP_MEMBER_REF,0: "2"
 533         4 USER,1701: "picard"
 534         5    (4) USER_GROUP_MEMBER_REF,0: "2"
 535         6    (4) USER_PASSWORD,0: "engage"
 536         3    (1) USER_PASSWORD,0: "hacktheplanet"
 537         THATSALL
 538         # get_cnf user 1337
 539         1 USER,1337: "l33t_h4x0r"
 540         2    (1) USER_GROUP_MEMBER_REF,0: "2"
 541         3    (1) USER_PASSWORD,0: "hacktheplanet"
 542         # get_cnf user 1701
 543         1 USER,1701: "picard"
 544         2    (1) USER_GROUP_MEMBER_REF,0: "2"
 545         3    (1) USER_PASSWORD,0: "engage"
 546
 547     It is a limitation of ``cnfvar.py`` that it cannot parse CNF data
 548     structured like the above example: child lists are only populated from
 549     subsequent CNF vars using the parent number solely to track nesting levels.
 550     The parser does not keep track of line numbers while traversing the input
 551     so it doesn’t support retroactively assigning a child to anything else but
 552     the immediate parent.
 553     """
 554     lines = []
 555     current = get(state)
 556     while True:
 557         cnf_line = read_child_line(current)
 558         if cnf_line is not None:
 559             lines.append(cnf_line)
 560             state = advance(state)
 561             if state is None:
 562                 break
 563             current = get(state)
 564             new_parent = get_parent(current)
 565             if new_parent is None:
 566                 # drop stack
 567                 return (state, lines, None)
 568             if new_parent > parent:
 569                 # parent is further down in hierarchy -> new level
 570                 (state, children, new_parent) = \
 571                     parse_cnf_children (state, new_parent)
 572                 if state is None:
 573                     break
 574                 cnf_line["children"] = children
 575                 current = get(state)
 576                 new_parent = get_parent(current)
 577                 if new_parent is None:
 578                     # drop stack
 579                     return (state, lines, None)
 580             if new_parent < parent:
 581                 # parent is further up in hierarchy -> pop level
 582                 return (state, lines, new_parent)
 583             # new_parent == parent -> continue parsing on same level
 584     return (state, lines, parent)
 585
 586
 587 def get_parent(line):
 588     """
 589     Extract the ID of the parent for a given CNF line.
 590
 591     :param str line: CNF line
 592     :returns: parent ID or None if no parent is found
 593     :rtype: int or None
 594     """
 595     match = re.match(grab_parent_pattern, line)
 596     if match is None:  # -> no parent
 597         return None
 598     return int(match.groups()[0])
 599
 600
 601 def read_base_line(line):
 602     """
 603     Turn one top-level CNF line into a dictionary.
 604
 605     :param str line: CNF line
 606     :rtype: {str: Any}
 607
 608     This performs the necessary decoding on values to obtain proper Python
 609     strings from 8-bit encoded CNF data.
 610
 611     The function only operates on individual lines. Argument strings that
 612     contain data for multiple lines – this includes child lines of the current
 613     CNF var! – will trigger a parsing exception.
 614     """
 615     if len(line.strip()) == 0:
 616         return None  # ignore empty lines
 617     if line[0] == b"#":
 618         return None  # ignore comments
 619
 620     match = re.match(base_line_pattern, line)
 621     if match is None:
 622         raise MalformedCNF("Syntax error in line \"\"\"%s\"\"\"" % line)
 623     number, varname, instance, data, comment = match.groups()
 624     return {
 625         "number"   : marshal_in_number   (number),
 626         "varname"  : marshal_in_varname  (varname),
 627         "instance" : marshal_in_instance (instance),
 628         "data"     : marshal_in_data     (data),
 629         "comment"  : marshal_in_comment  (comment),
 630     }
 631
 632
 633 def read_child_line(line):
 634     """
 635     Turn one child CNF line into a dictionary.
 636
 637     :param str line: CNF line
 638     :rtype: {str: Any}
 639
 640     This function only operates on individual lines. If the argument string is
 641     syntactically valid but contains input representing multiple CNF vars, a
 642     parse error will be thrown.
 643     """
 644     if len(line.strip()) == 0:
 645         return None  # ignore empty lines
 646     if line[0] == "#":
 647         return None  # ignore comments
 648
 649     match = re.match(child_line_pattern, line)
 650     if match is None:
 651         raise MalformedCNF("Syntax error in child line \"\"\"%s\"\"\""
 652                            % from_latin1 (line))
 653     number, parent, varname, instance, data, comment = match.groups()
 654     return {
 655         "number"   : marshal_in_number   (number),
 656         "parent"   : marshal_in_parent   (parent),
 657         "varname"  : marshal_in_varname  (varname),
 658         "instance" : marshal_in_instance (instance),
 659         "data"     : marshal_in_data     (data),
 660         "comment"  : marshal_in_comment  (comment),
 661     }
 662
 663
 664 ###############################################################################
 665 # SERIALIZATION
 666 ###############################################################################
 667
 668
 669 def cnf_root(root):
 670     """
 671     Extract a list of CNFs from a given structure.
 672
 673     :param root: list of CNFs or a CNF dictionary
 674     :type root: [dict] or dict
 675     :raises: :py:class:`TypeError` if no CNFs can be extracted
 676     :returns: list with one or more CNF objects
 677     :rtype: [dict]
 678
 679     Output varies depending on a few conditions:
 680     - If `root` is a list, return it right away
 681     - If `root` is a dict corresponding to a valid CNF value, return it wrapped
 682       in a list
 683     - If `root` is a dict with a `cnf` key containg a list (as the JSON
 684       returned by `get_cnf -j`), return the value
 685     - Otherwise, raise an error
 686     """
 687     if isinstance(root, list):
 688         return root
 689     if not isinstance(root, dict):
 690         raise TypeError(
 691             "Expected dictionary of CNF_VARs, got %s." % type(root))
 692     if is_cnf_var(root):
 693         return [root]
 694     cnf = root.get("cnf", None)
 695     if not isinstance(cnf, list):
 696         raise TypeError("Expected list of CNF_VARs, got %s." % type(cnf))
 697     return cnf
 698
 699
 700 ###############################################################################
 701 # TRAVERSAL
 702 ###############################################################################
 703
 704
 705 def walk_cnf(cnf, nested, fun, acc):
 706     """
 707     Depth-first traversal of a CNF tree.
 708
 709     :type cnf: cnf list
 710     :type nested: bool
 711     :type fun: 'a -> bool -> (cnf stuff) -> 'a
 712     :type acc: 'a
 713     :rtype: 'a
 714
 715     Executes ``fun`` recursively for each node in the tree. The function
 716     receives the accumulator ``acc`` which can be of an arbitrary type as first
 717     argument. The second argument is a flag indicating whether the current
 718     CNF var is a child (if ``True``) or a parent var. CNF member fields are
 719     passed via named optional arguments.
 720     """
 721     for var in cnf:
 722         acc = fun(acc,
 723                   nested,
 724                   comment=var.get("comment", None),
 725                   data=var.get("data", None),
 726                   instance=var.get("instance", None),
 727                   number=var.get("number", None),
 728                   parent=var.get("parent", None),
 729                   varname=var.get("varname", None))
 730         children = var.get("children", None)
 731         if children is not None:
 732             acc = walk_cnf(children, True, fun, acc)
 733     return acc