lib/lyx2lyx/parser_tools.py

   1 # This file is part of lyx2lyx
   2 # -*- coding: utf-8 -*-
   3 # Copyright (C) 2002-2011 Dekel Tsur <dekel@lyx.org>,
   4 # José Matos <jamatos@lyx.org>, Richard Heck <rgheck@comcast.net>
   5 #
   6 # This program is free software; you can redistribute it and/or
   7 # modify it under the terms of the GNU General Public License
   8 # as published by the Free Software Foundation; either version 2
   9 # of the License, or (at your option) any later version.
  10 #
  11 # This program is distributed in the hope that it will be useful,
  12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 # GNU General Public License for more details.
  15 #
  16 # You should have received a copy of the GNU General Public License
  17 # along with this program; if not, write to the Free Software
  18 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  19
  20
  21 """
  22 This module offers several free functions to help parse lines.
  23 More documentaton is below, but here is a quick guide to what
  24 they do. Optional arguments are marked by brackets.
  25
  26 find_token(lines, token[, start[, end[, ignorews]]]):
  27   Returns the first line i, start <= i < end, on which
  28   token is found at the beginning. Returns -1 if not
  29   found.
  30   If ignorews is (given and) True, then differences
  31   in whitespace do not count, except that there must be no
  32   extra whitespace following token itself.
  33
  34 find_token_exact(lines, token[, start[, end]]]):
  35   As find_token, but with ignorews set to True.
  36
  37 find_tokens(lines, tokens[, start[, end[, ignorews]]]):
  38   Returns the first line i, start <= i < end, on which
  39   one of the tokens in tokens is found at the beginning.
  40   Returns -1 if not found.
  41   If ignorews is (given and) True, then differences
  42   in whitespace do not count, except that there must be no
  43   extra whitespace following token itself.
  44
  45 find_tokens_exact(lines, token[, start[, end]]):
  46   As find_tokens, but with ignorews True.
  47
  48 find_token_backwards(lines, token, start):
  49 find_tokens_backwards(lines, tokens, start):
  50   As before, but look backwards.
  51
  52 find_substring(lines, sub[, start[, end]]) -> int
  53   As find_token, but sub may be anywhere in the line.
  54
  55 find_re(lines, rexp, start[, end]):
  56   As find_token, but rexp is a regular expression object,
  57   so it has to be passed as e.g.: re.compile(r'...').
  58
  59 get_value(lines, token[, start[, end[, default[, delete]]]]):
  60   Similar to find_token, but it returns what follows the
  61   token on the found line. Example:
  62     get_value(document.header, "\\use_xetex", 0)
  63   will find a line like:
  64     \\use_xetex true
  65   and, in that case, return "true". (Note that whitespace
  66   is stripped.) The final argument, default, defaults to "",
  67   and is what is returned if we do not find anything. So you
  68   can use that to set a default.
  69
  70 get_quoted_value(lines, token[, start[, end[, default[, delete]]]]):
  71   Similar to get_value, but it will strip quotes off the
  72   value, if they are present. So use this one for cases
  73   where the value is normally quoted.
  74
  75 get_option_value(line, option):
  76   This assumes we have a line with something like:
  77       option="value"
  78   and returns value. Returns "" if not found.
  79
  80 get_bool_value(lines, token[, start[, end[, default, delete]]]]):
  81   Like get_value, but returns a boolean.
  82
  83 set_bool_value(lines, token, value[, start[, end]]):
  84   Find `token` in `lines[start:end]` and set to boolean value bool(`value`).
  85   Return old value. Raise ValueError if token is not in lines.
  86
  87 del_token(lines, token[, start[, end]]):
  88   Like find_token, but deletes the line if it finds one.
  89   Returns True if a line got deleted, otherwise False.
  90
  91   Use get_* with the optional argument "delete=True", if you want to
  92   get and delete a token.
  93
  94 find_beginning_of(lines, i, start_token, end_token):
  95   Here, start_token and end_token are meant to be a matching
  96   pair, like "\\begin_layout" and "\\end_layout". We look for
  97   the start_token that pairs with the end_token that occurs
  98   on or after line i. Returns -1 if not found.
  99   So, in the layout case, this would find the \\begin_layout
 100   for the layout line i is in.
 101   Example:
 102     ec = find_token(document.body, "</cell", i)
 103     bc = find_beginning_of(document.body, ec, \
 104         "<cell", "</cell")
 105   Now, assuming no -1s, bc-ec wraps the cell for line i.
 106
 107 find_end_of(lines, i, start_token, end_token):
 108   Like find_beginning_of, but looking for the matching
 109   end_token. This might look like:
 110     bc = find_token_(document.body, "<cell", i)
 111     ec = find_end_of(document.body, bc,  "<cell", "</cell")
 112   Now, assuming no -1s, bc-ec wrap the next cell.
 113
 114 find_end_of_inset(lines, i):
 115   Specialization of find_end_of for insets.
 116
 117 find_end_of_layout(lines, i):
 118   Specialization of find_end_of for layouts.
 119
 120 find_end_of_sequence(lines, i):
 121   Find the end of the sequence of layouts of the same kind.
 122   Considers nesting. If the last paragraph in sequence is nested,
 123   the position of the last \end_deeper is returned, else
 124   the position of the last \end_layout.
 125
 126 is_in_inset(lines, i, inset, default=(-1,-1)):
 127   Check if line i is in an inset of the given type.
 128   If so, returns starting and ending lines. Otherwise,
 129   return default.
 130   Example:
 131     is_in_inset(document.body, i, "\\begin_inset Tabular")
 132   returns (-1,-1) unless i is within a table. If it is, then
 133   it returns the line on which the table begins and the one
 134   on which it ends. Note that this pair will evaulate to
 135   boolean True, so
 136     if is_in_inset(..., default=False):
 137   will do what you expect.
 138
 139 get_containing_inset(lines, i):
 140   Finds out what kind of inset line i is within. Returns a
 141   list containing what follows \begin_inset on the line
 142   on which the inset begins, plus the starting and ending line.
 143   Returns False on any kind of error or if it isn't in an inset.
 144   So get_containing_inset(document.body, i) might return:
 145     ("CommandInset ref", 300, 306)
 146   if i is within an InsetRef beginning on line 300 and ending
 147   on line 306.
 148
 149 get_containing_layout(lines, i):
 150   As get_containing_inset, but for layout. Additionally returns the
 151   position of real paragraph start (after par params) as 4th value.
 152
 153 find_nonempty_line(lines, start[, end):
 154   Finds the next non-empty line.
 155
 156 check_token(line, token):
 157   Does line begin with token?
 158
 159 is_nonempty_line(line):
 160   Does line contain something besides whitespace?
 161
 162 count_pars_in_inset(lines, i):
 163   Counts the paragraphs inside an inset.
 164
 165 """
 166
 167 import re
 168
 169 # Utilities for one line
 170 def check_token(line, token):
 171     """ check_token(line, token) -> bool
 172
 173     Return True if token is present in line and is the first element
 174     else returns False.
 175
 176     Deprecated. Use line.startswith(token).
 177     """
 178     return line.startswith(token)
 179
 180
 181 def is_nonempty_line(line):
 182     """ is_nonempty_line(line) -> bool
 183
 184     Return False if line is either empty or it has only whitespaces,
 185     else return True."""
 186     return bool(line.strip())
 187
 188
 189 # Utilities for a list of lines
 190 def find_token(lines, token, start=0, end=0, ignorews=False):
 191     """ find_token(lines, token, start[[, end], ignorews]) -> int
 192
 193     Return the lowest line where token is found, and is the first
 194     element, in lines[start, end].
 195
 196     If ignorews is True (default is False), then differences in
 197     whitespace are ignored, but there must be whitespace following
 198     token itself.
 199
 200     Use find_substring(lines, sub) to find a substring anywhere in `lines`.
 201
 202     Return -1 on failure."""
 203
 204     if end == 0 or end > len(lines):
 205         end = len(lines)
 206     if ignorews:
 207         y = token.split()
 208     for i in range(start, end):
 209         if ignorews:
 210             x = lines[i].split()
 211             if len(x) < len(y):
 212                 continue
 213             if x[:len(y)] == y:
 214                 return i
 215         else:
 216             if lines[i].startswith(token):
 217                 return i
 218     return -1
 219
 220
 221 def find_token_exact(lines, token, start=0, end=0):
 222     return find_token(lines, token, start, end, True)
 223
 224
 225 def find_tokens(lines, tokens, start=0, end=0, ignorews=False):
 226     """ find_tokens(lines, tokens, start[[, end], ignorews]) -> int
 227
 228     Return the lowest line where one token in tokens is found, and is
 229     the first element, in lines[start, end].
 230
 231     Return -1 on failure."""
 232
 233     if end == 0 or end > len(lines):
 234         end = len(lines)
 235
 236     for i in range(start, end):
 237         for token in tokens:
 238             if ignorews:
 239                 x = lines[i].split()
 240                 y = token.split()
 241                 if len(x) < len(y):
 242                     continue
 243                 if x[:len(y)] == y:
 244                     return i
 245             else:
 246                 if lines[i].startswith(token):
 247                     return i
 248     return -1
 249
 250
 251 def find_tokens_exact(lines, tokens, start=0, end=0):
 252     return find_tokens(lines, tokens, start, end, True)
 253
 254
 255 def find_substring(lines, sub, start=0, end=0):
 256     """ find_substring(lines, sub[, start[, end]]) -> int
 257
 258     Return the lowest line number `i` in [start, end] where
 259     `sub` is a substring of line[i].
 260
 261     Return -1 on failure."""
 262
 263     if end == 0 or end > len(lines):
 264         end = len(lines)
 265     for i in range(start, end):
 266         if sub in lines[i]:
 267                 return i
 268     return -1
 269
 270
 271 def find_re(lines, rexp, start=0, end=0):
 272     """ find_re(lines, rexp[, start[, end]]) -> int
 273
 274     Return the lowest line number `i` in [start, end] where the regular
 275     expression object `rexp` matches at the beginning of line[i].
 276     Return -1 on failure.
 277
 278     Start your pattern with the wildcard ".*" to find a match anywhere in a
 279     line. Use find_substring() to find a substring anywhere in the lines.
 280     """
 281     if end == 0 or end > len(lines):
 282         end = len(lines)
 283     for i in range(start, end):
 284         if rexp.match(lines[i]):
 285                 return i
 286     return -1
 287
 288
 289 def find_token_backwards(lines, token, start):
 290     """ find_token_backwards(lines, token, start) -> int
 291
 292     Return the highest line where token is found, and is the first
 293     element, in lines[start, end].
 294
 295     Return -1 on failure."""
 296     for i in range(start, -1, -1):
 297         if lines[i].startswith(token):
 298             return i
 299     return -1
 300
 301
 302 def find_tokens_backwards(lines, tokens, start):
 303     """ find_tokens_backwards(lines, token, start) -> int
 304
 305     Return the highest line where token is found, and is the first
 306     element, in lines[end, start].
 307
 308     Return -1 on failure."""
 309     for i in range(start, -1, -1):
 310         line = lines[i]
 311         for token in tokens:
 312             if line.startswith(token):
 313                 return i
 314     return -1
 315
 316
 317 def find_complete_lines(lines, sublines, start=0, end=0):
 318     """Find first occurence of sequence `sublines` in list `lines`.
 319     Return index of first line or -1 on failure.
 320
 321     Efficient search for a sub-list in a large list. Works for any values.
 322
 323     >>> find_complete_lines([1, 2, 3, 1, 1, 2], [1, 2])
 324     0
 325
 326     The `start` and `end` arguments work similar to list.index()
 327
 328     >>> find_complete_lines([1, 2, 3, 1, 1 ,2], [1, 2], start=1)
 329     4
 330     >>> find_complete_lines([1, 2, 3, 1, 1 ,2], [1, 2], start=1, end=4)
 331     -1
 332
 333     The return value can be used to substitute the sub-list.
 334     Take care to check before use:
 335
 336     >>> l = [1, 1, 2]
 337     >>> s = find_complete_lines(l, [1, 2])
 338     >>> if s != -1:
 339     ...     l[s:s+2] = [3]; l
 340     [1, 3]
 341
 342     See also del_complete_lines().
 343     """
 344     if not sublines:
 345         return start
 346     end = end or len(lines)
 347     N = len(sublines)
 348     try:
 349         while True:
 350             for j, value in enumerate(sublines):
 351                 i = lines.index(value, start, end)
 352                 if j and i != start:
 353                     start = i-j
 354                     break
 355                 start = i + 1
 356             else:
 357                 return i +1 - N
 358     except ValueError: # `sublines` not found
 359         return -1
 360
 361
 362 def find_across_lines(lines, sub, start=0, end=0):
 363     sublines = sub.splitlines()
 364     if len(sublines) > 2:
 365         # at least 3 lines: the middle one(s) are complete -> use index search
 366         i = find_complete_lines(lines, sublines[1:-1], start+1, end-1)
 367         if i < start+1:
 368             return -1
 369         try:
 370             if (lines[i-1].endswith(sublines[0]) and
 371                 lines[i+len(sublines)].startswith(sublines[-1])):
 372                 return i-1
 373         except IndexError:
 374             pass
 375     elif len(sublines) > 1:
 376         # last subline must start a line
 377         i = find_token(lines, sublines[-1], start, end)
 378         if i < start + 1:
 379             return -1
 380         if lines[i-1].endswith(sublines[0]):
 381             return i-1
 382     else: # no line-break, may be in the middle of a line
 383         if end == 0 or end > len(lines):
 384             end = len(lines)
 385         for i in range(start, end):
 386             if sub in lines[i]:
 387                 return i
 388     return -1
 389
 390
 391 def get_value(lines, token, start=0, end=0, default="", delete=False):
 392     """Find `token` in `lines` and return part of line that follows it.
 393
 394     Find the next line that looks like:
 395       token followed by other stuff
 396
 397     If `delete` is True, delete the line (if found).
 398
 399     Return "followed by other stuff" with leading and trailing
 400     whitespace removed.
 401     """
 402     i = find_token_exact(lines, token, start, end)
 403     if i == -1:
 404         return default
 405     # TODO: establish desired behaviour, eventually change to
 406     #  return lines.pop(i)[len(token):].strip() # or default
 407     # see test_parser_tools.py
 408     l = lines[i].split(None, 1)
 409     if delete:
 410         del(lines[i])
 411     if len(l) > 1:
 412         return l[1].strip()
 413     return default
 414
 415
 416 def get_quoted_value(lines, token, start=0, end=0, default="", delete=False):
 417     """ get_quoted_value(lines, token, start[[, end], default]) -> string
 418
 419     Find the next line that looks like:
 420       token "followed by other stuff"
 421     Returns "followed by other stuff" with leading and trailing
 422     whitespace and quotes removed. If there are no quotes, that is OK too.
 423     So use get_value to preserve possible quotes, this one to remove them,
 424     if they are there.
 425     Note that we will NOT strip quotes from default!
 426     """
 427     val = get_value(lines, token, start, end, "", delete)
 428     if not val:
 429       return default
 430     return val.strip('"')
 431
 432
 433 bool_values = {"true": True, "1": True,
 434                "false": False, "0": False}
 435
 436 def get_bool_value(lines, token, start=0, end=0, default=None, delete=False):
 437     """ get_bool_value(lines, token, start[[, end], default]) -> string
 438
 439     Find the next line that looks like:
 440       `token` <bool_value>
 441
 442     Return True if <bool_value> is 1 or "true", False if <bool_value>
 443     is 0 or "false", else `default`.
 444     """
 445     val = get_quoted_value(lines, token, start, end, default, delete)
 446     return bool_values.get(val, default)
 447
 448
 449 def set_bool_value(lines, token, value, start=0, end=0):
 450     """Find `token` in `lines` and set to bool(`value`).
 451
 452     Return previous value. Raise `ValueError` if `token` is not in lines.
 453
 454     Cf. find_token(), get_bool_value().
 455     """
 456     i = find_token(lines, token, start, end)
 457     if i == -1:
 458         raise ValueError
 459     oldvalue = get_bool_value(lines, token, i, i+1)
 460     if oldvalue is value:
 461         return oldvalue
 462     # set to new value
 463     if get_quoted_value(lines, token, i, i+1) in ('0', '1'):
 464         lines[i] = "%s %d" % (token, value)
 465     else:
 466         lines[i] = "%s %s" % (token, str(value).lower())
 467
 468     return oldvalue
 469
 470
 471 def get_option_value(line, option):
 472     rx = option + '\s*=\s*"([^"]+)"'
 473     rx = re.compile(rx)
 474     m = rx.search(line)
 475     if not m:
 476       return ""
 477     return m.group(1)
 478
 479
 480 def set_option_value(line, option, value):
 481     rx = '(' + option + '\s*=\s*")[^"]+"'
 482     rx = re.compile(rx)
 483     m = rx.search(line)
 484     if not m:
 485         return line
 486     return re.sub(rx, '\g<1>' + value + '"', line)
 487
 488
 489 def del_token(lines, token, start=0, end=0):
 490     """ del_token(lines, token, start, end) -> int
 491
 492     Find the first line in lines where token is the first element
 493     and delete that line. Returns True if we deleted a line, False
 494     if we did not."""
 495
 496     k = find_token_exact(lines, token, start, end)
 497     if k == -1:
 498         return False
 499     del lines[k]
 500     return True
 501
 502 def del_complete_lines(lines, sublines, start=0, end=0):
 503     """Delete first occurence of `sublines` in list `lines`.
 504
 505     Efficient deletion of a sub-list in a list. Works for any values.
 506     The `start` and `end` arguments work similar to list.index()
 507
 508     Returns True if a deletion was done and False if not.
 509
 510     >>> l = [1, 0, 1, 1, 1, 2]
 511     >>> del_complete_lines(l, [0, 1, 1])
 512     True
 513     >>> l
 514     [1, 1, 2]
 515     """
 516     i = find_complete_lines(lines, sublines, start, end)
 517     if i == -1:
 518         return False
 519     del(lines[i:i+len(sublines)])
 520     return True
 521
 522
 523 def del_value(lines, token, start=0, end=0, default=None):
 524     """
 525     Find the next line that looks like:
 526       token followed by other stuff
 527     Delete that line and return "followed by other stuff"
 528     with leading and trailing whitespace removed.
 529
 530     If token is not found, return `default`.
 531     """
 532     i = find_token_exact(lines, token, start, end)
 533     if i == -1:
 534         return default
 535     return lines.pop(i)[len(token):].strip()
 536
 537
 538 def find_beginning_of(lines, i, start_token, end_token):
 539     count = 1
 540     while i > 0:
 541         i = find_tokens_backwards(lines, [start_token, end_token], i-1)
 542         if i == -1:
 543             return -1
 544         if lines[i].startswith(end_token):
 545             count = count+1
 546         else:
 547             count = count-1
 548         if count == 0:
 549             return i
 550     return -1
 551
 552
 553 def find_end_of(lines, i, start_token, end_token):
 554     count = 1
 555     n = len(lines)
 556     while i < n:
 557         i = find_tokens(lines, [end_token, start_token], i+1)
 558         if i == -1:
 559             return -1
 560         if lines[i].startswith(start_token):
 561             count = count+1
 562         else:
 563             count = count-1
 564         if count == 0:
 565             return i
 566     return -1
 567
 568
 569 def find_nonempty_line(lines, start=0, end=0):
 570     if end == 0:
 571         end = len(lines)
 572     for i in range(start, end):
 573         if lines[i].strip():
 574             return i
 575     return -1
 576
 577
 578 def find_end_of_inset(lines, i):
 579     " Find end of inset, where lines[i] is included."
 580     return find_end_of(lines, i, "\\begin_inset", "\\end_inset")
 581
 582
 583 def find_end_of_layout(lines, i):
 584     " Find end of layout, where lines[i] is included."
 585     return find_end_of(lines, i, "\\begin_layout", "\\end_layout")
 586
 587
 588 def is_in_inset(lines, i, inset, default=(-1,-1)):
 589     """
 590     Check if line i is in an inset of the given type.
 591     If so, return starting and ending lines, otherwise `default`.
 592     Example:
 593       is_in_inset(document.body, i, "\\begin_inset Tabular")
 594     returns (-1,-1) if `i` is not within a "Tabular" inset (i.e. a table).
 595     If it is, then it returns the line on which the table begins and the one
 596     on which it ends.
 597     Note that this pair will evaulate to boolean True, so (with the optional
 598     default value set to False)
 599       if is_in_inset(..., default=False):
 600     will do what you expect.
 601     """
 602     start = find_token_backwards(lines, inset, i)
 603     if start == -1:
 604       return default
 605     end = find_end_of_inset(lines, start)
 606     if end < i: # this includes the notfound case.
 607       return default
 608     return (start, end)
 609
 610
 611 def get_containing_inset(lines, i):
 612   '''
 613   Finds out what kind of inset line i is within. Returns a
 614   list containing (i) what follows \begin_inset on the line
 615   on which the inset begins, plus the starting and ending line.
 616   Returns False on any kind of error or if it isn't in an inset.
 617   '''
 618   j = i
 619   while True:
 620       stins = find_token_backwards(lines, "\\begin_inset", j)
 621       if stins == -1:
 622           return False
 623       endins = find_end_of_inset(lines, stins)
 624       if endins > j:
 625           break
 626       j = stins - 1
 627
 628   if endins < i:
 629       return False
 630
 631   inset = get_value(lines, "\\begin_inset", stins)
 632   if inset == "":
 633       # shouldn't happen
 634       return False
 635   return (inset, stins, endins)
 636
 637
 638 def get_containing_layout(lines, i):
 639   '''
 640   Find out what kind of layout line `i` is within.
 641   Return a tuple
 642     (layoutname, layoutstart, layoutend, startofcontent)
 643   containing
 644     * layout style/name,
 645     * start line number,
 646     * end line number, and
 647     * number of first paragraph line (after all params).
 648   Return `False` on any kind of error.
 649   '''
 650   j = i
 651   while True:
 652       stlay = find_token_backwards(lines, "\\begin_layout", j)
 653       if stlay == -1:
 654           return False
 655       endlay = find_end_of_layout(lines, stlay)
 656       if endlay > i:
 657           break
 658       j = stlay - 1
 659
 660   if endlay < i:
 661       return False
 662
 663   layoutname = get_value(lines, "\\begin_layout", stlay)
 664   if layoutname == "": # layout style missing
 665       # TODO: What shall we do in this case?
 666       pass
 667       # layoutname == "Standard" # use same fallback as the LyX parser:
 668       # raise ValueError("Missing layout name on line %d"%stlay) # diagnosis
 669       # return False # generic error response
 670   par_params = ["\\noindent", "\\indent", "\\indent-toggle", "\\leftindent",
 671                 "\\start_of_appendix", "\\paragraph_spacing", "\\align",
 672                 "\\labelwidthstring"]
 673   stpar = stlay
 674   while True:
 675       stpar += 1
 676       if lines[stpar].split(' ', 1)[0] not in par_params:
 677           break
 678   return (layoutname, stlay, endlay, stpar)
 679
 680
 681 def count_pars_in_inset(lines, i):
 682   '''
 683   Counts the paragraphs within this inset
 684   '''
 685   ins = get_containing_inset(lines, i)
 686   if ins == -1:
 687       return -1
 688   pars = 0
 689   for j in range(ins[1], ins[2]):
 690       m = re.match(r'\\begin_layout (.*)', lines[j])
 691       if m and get_containing_inset(lines, j)[0] == ins[0]:
 692           pars += 1
 693
 694   return pars
 695
 696
 697 def find_end_of_sequence(lines, i):
 698   '''
 699   Returns the end of a sequence of identical layouts.
 700   '''
 701   lay = get_containing_layout(lines, i)
 702   if lay == False:
 703       return -1
 704   layout = lay[0]
 705   endlay = lay[2]
 706   i = endlay
 707   while True:
 708       m = re.match(r'\\begin_layout (.*)', lines[i])
 709       if m and m.group(1) != layout:
 710           return endlay
 711       elif lines[i] == "\\begin_deeper":
 712           j = find_end_of(lines, i, "\\begin_deeper", "\\end_deeper")
 713           if j != -1:
 714               i = j
 715               endlay = j
 716               continue
 717       if m and m.group(1) == layout:
 718           endlay = find_end_of_layout(lines, i)
 719           i = endlay
 720           continue
 721       if i == len(lines) - 1:
 722           break
 723       i = i + 1
 724
 725   return endlay