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     if end == 0 or end > len(lines):
 233         end = len(lines)
 234
 235     for i in range(start, end):
 236         for token in tokens:
 237             if ignorews:
 238                 x = lines[i].split()
 239                 y = token.split()
 240                 if len(x) < len(y):
 241                     continue
 242                 if x[:len(y)] == y:
 243                     return i
 244             else:
 245                 if lines[i].startswith(token):
 246                     return i
 247     return -1
 248
 249
 250 def find_tokens_exact(lines, tokens, start=0, end=0):
 251     return find_tokens(lines, tokens, start, end, True)
 252
 253
 254 def find_substring(lines, sub, start=0, end=0):
 255     """ find_substring(lines, sub[, start[, end]]) -> int
 256
 257     Return the lowest line number `i` in [start, end] where
 258     `sub` is a substring of line[i].
 259
 260     Return -1 on failure."""
 261
 262     if end == 0 or end > len(lines):
 263         end = len(lines)
 264     for i in range(start, end):
 265         if sub in lines[i]:
 266                 return i
 267     return -1
 268
 269
 270 def find_re(lines, rexp, start=0, end=0):
 271     """ find_re(lines, rexp[, start[, end]]) -> int
 272
 273     Return the lowest line number `i` in [start, end] where the regular
 274     expression object `rexp` matches at the beginning of line[i].
 275     Return -1 on failure.
 276
 277     Start your pattern with the wildcard ".*" to find a match anywhere in a
 278     line. Use find_substring() to find a substring anywhere in the lines.
 279     """
 280     if end == 0 or end > len(lines):
 281         end = len(lines)
 282     for i in range(start, end):
 283         if rexp.match(lines[i]):
 284                 return i
 285     return -1
 286
 287
 288 def find_token_backwards(lines, token, start):
 289     """ find_token_backwards(lines, token, start) -> int
 290
 291     Return the highest line where token is found, and is the first
 292     element, in lines[start, end].
 293
 294     Return -1 on failure."""
 295     for i in range(start, -1, -1):
 296         if lines[i].startswith(token):
 297             return i
 298     return -1
 299
 300
 301 def find_tokens_backwards(lines, tokens, start):
 302     """ find_tokens_backwards(lines, token, start) -> int
 303
 304     Return the highest line where token is found, and is the first
 305     element, in lines[end, start].
 306
 307     Return -1 on failure."""
 308     for i in range(start, -1, -1):
 309         line = lines[i]
 310         for token in tokens:
 311             if line.startswith(token):
 312                 return i
 313     return -1
 314
 315
 316 def find_complete_lines(lines, sublines, start=0, end=0):
 317     """Find first occurence of sequence `sublines` in list `lines`.
 318     Return index of first line or -1 on failure.
 319
 320     Efficient search for a sub-list in a large list. Works for any values.
 321
 322     >>> find_complete_lines([1, 2, 3, 1, 1, 2], [1, 2])
 323     0
 324
 325     The `start` and `end` arguments work similar to list.index()
 326
 327     >>> find_complete_lines([1, 2, 3, 1, 1 ,2], [1, 2], start=1)
 328     4
 329     >>> find_complete_lines([1, 2, 3, 1, 1 ,2], [1, 2], start=1, end=4)
 330     -1
 331
 332     The return value can be used to substitute the sub-list.
 333     Take care to check before use:
 334
 335     >>> l = [1, 1, 2]
 336     >>> s = find_complete_lines(l, [1, 2])
 337     >>> if s != -1:
 338     ...     l[s:s+2] = [3]; l
 339     [1, 3]
 340
 341     See also del_complete_lines().
 342     """
 343     if not sublines:
 344         return start
 345     end = end or len(lines)
 346     N = len(sublines)
 347     try:
 348         while True:
 349             for j, value in enumerate(sublines):
 350                 i = lines.index(value, start, end)
 351                 if j and i != start:
 352                     start = i-j
 353                     break
 354                 start = i + 1
 355             else:
 356                 return i +1 - N
 357     except ValueError: # `sublines` not found
 358         return -1
 359
 360
 361 def find_across_lines(lines, sub, start=0, end=0):
 362     sublines = sub.splitlines()
 363     if len(sublines) > 2:
 364         # at least 3 lines: the middle one(s) are complete -> use index search
 365         i = find_complete_lines(lines, sublines[1:-1], start+1, end-1)
 366         if i < start+1:
 367             return -1
 368         try:
 369             if (lines[i-1].endswith(sublines[0]) and
 370                 lines[i+len(sublines)].startswith(sublines[-1])):
 371                 return i-1
 372         except IndexError:
 373             pass
 374     elif len(sublines) > 1:
 375         # last subline must start a line
 376         i = find_token(lines, sublines[-1], start, end)
 377         if i < start + 1:
 378             return -1
 379         if lines[i-1].endswith(sublines[0]):
 380             return i-1
 381     else: # no line-break, may be in the middle of a line
 382         if end == 0 or end > len(lines):
 383             end = len(lines)
 384         for i in range(start, end):
 385             if sub in lines[i]:
 386                 return i
 387     return -1
 388
 389
 390 def get_value(lines, token, start=0, end=0, default="", delete=False):
 391     """Find `token` in `lines` and return part of line that follows it.
 392
 393     Find the next line that looks like:
 394       token followed by other stuff
 395
 396     If `delete` is True, delete the line (if found).
 397
 398     Return "followed by other stuff" with leading and trailing
 399     whitespace removed.
 400     """
 401     i = find_token_exact(lines, token, start, end)
 402     if i == -1:
 403         return default
 404     # TODO: establish desired behaviour, eventually change to
 405     #  return lines.pop(i)[len(token):].strip() # or default
 406     # see test_parser_tools.py
 407     l = lines[i].split(None, 1)
 408     if delete:
 409         del(lines[i])
 410     if len(l) > 1:
 411         return l[1].strip()
 412     return default
 413
 414
 415 def get_quoted_value(lines, token, start=0, end=0, default="", delete=False):
 416     """ get_quoted_value(lines, token, start[[, end], default]) -> string
 417
 418     Find the next line that looks like:
 419       token "followed by other stuff"
 420     Returns "followed by other stuff" with leading and trailing
 421     whitespace and quotes removed. If there are no quotes, that is OK too.
 422     So use get_value to preserve possible quotes, this one to remove them,
 423     if they are there.
 424     Note that we will NOT strip quotes from default!
 425     """
 426     val = get_value(lines, token, start, end, "", delete)
 427     if not val:
 428       return default
 429     return val.strip('"')
 430
 431 bool_values = {True:  ("true", "1"),
 432                False: ("false", "0")}
 433
 434 def get_bool_value(lines, token, start=0, end=0, default=None, delete=False):
 435     """ get_bool_value(lines, token, start[[, end], default]) -> string
 436
 437     Find the next line that looks like:
 438       token <bool_value>
 439
 440     Return True if <bool_value> is 1 or "true", False if bool_value
 441     is 0 or "false", else `default`.
 442     """
 443
 444     val = get_quoted_value(lines, token, start, end, default, delete)
 445     if val in bool_values[True]:
 446         return True
 447     if val in bool_values[False]:
 448         return False
 449     return default
 450
 451
 452 def set_bool_value(lines, token, value, start=0, end=0):
 453     """Find `token` in `lines` and set to bool(`value`).
 454
 455     Return previous value. Raise `ValueError` if `token` is not in lines.
 456
 457     Cf. find_token(), get_bool_value().
 458     """
 459     i = find_token(lines, token, start, end)
 460     if i == -1:
 461         raise ValueError
 462     oldvalue = get_bool_value(lines, token, i, i+1)
 463     if oldvalue is value:
 464         return oldvalue
 465     # Use 0/1 or true/false?
 466     if get_quoted_value(lines, token, i, i+1) in ('0', '1'):
 467         value_string = bool_values[value][1]
 468     else:
 469         value_string = bool_values[value][0]
 470     # set to new value
 471     lines[i] = "%s %s" % (token, value_string)
 472
 473     return oldvalue
 474
 475
 476 def get_option_value(line, option):
 477     rx = option + '\s*=\s*"([^"]+)"'
 478     rx = re.compile(rx)
 479     m = rx.search(line)
 480     if not m:
 481       return ""
 482     return m.group(1)
 483
 484
 485 def set_option_value(line, option, value):
 486     rx = '(' + option + '\s*=\s*")[^"]+"'
 487     rx = re.compile(rx)
 488     m = rx.search(line)
 489     if not m:
 490         return line
 491     return re.sub(rx, '\g<1>' + value + '"', line)
 492
 493
 494 def del_token(lines, token, start=0, end=0):
 495     """ del_token(lines, token, start, end) -> int
 496
 497     Find the first line in lines where token is the first element
 498     and delete that line. Returns True if we deleted a line, False
 499     if we did not."""
 500
 501     k = find_token_exact(lines, token, start, end)
 502     if k == -1:
 503         return False
 504     del lines[k]
 505     return True
 506
 507 def del_complete_lines(lines, sublines, start=0, end=0):
 508     """Delete first occurence of `sublines` in list `lines`.
 509
 510     Efficient deletion of a sub-list in a list. Works for any values.
 511     The `start` and `end` arguments work similar to list.index()
 512
 513     Returns True if a deletion was done and False if not.
 514
 515     >>> l = [1, 0, 1, 1, 1, 2]
 516     >>> del_complete_lines(l, [0, 1, 1])
 517     True
 518     >>> l
 519     [1, 1, 2]
 520     """
 521     i = find_complete_lines(lines, sublines, start, end)
 522     if i == -1:
 523         return False
 524     del(lines[i:i+len(sublines)])
 525     return True
 526
 527
 528 def del_value(lines, token, start=0, end=0, default=None):
 529     """
 530     Find the next line that looks like:
 531       token followed by other stuff
 532     Delete that line and return "followed by other stuff"
 533     with leading and trailing whitespace removed.
 534
 535     If token is not found, return `default`.
 536     """
 537     i = find_token_exact(lines, token, start, end)
 538     if i == -1:
 539         return default
 540     return lines.pop(i)[len(token):].strip()
 541
 542
 543 def find_beginning_of(lines, i, start_token, end_token):
 544     count = 1
 545     while i > 0:
 546         i = find_tokens_backwards(lines, [start_token, end_token], i-1)
 547         if i == -1:
 548             return -1
 549         if lines[i].startswith(end_token):
 550             count = count+1
 551         else:
 552             count = count-1
 553         if count == 0:
 554             return i
 555     return -1
 556
 557
 558 def find_end_of(lines, i, start_token, end_token):
 559     count = 1
 560     n = len(lines)
 561     while i < n:
 562         i = find_tokens(lines, [end_token, start_token], i+1)
 563         if i == -1:
 564             return -1
 565         if lines[i].startswith(start_token):
 566             count = count+1
 567         else:
 568             count = count-1
 569         if count == 0:
 570             return i
 571     return -1
 572
 573
 574 def find_nonempty_line(lines, start=0, end=0):
 575     if end == 0:
 576         end = len(lines)
 577     for i in range(start, end):
 578         if lines[i].strip():
 579             return i
 580     return -1
 581
 582
 583 def find_end_of_inset(lines, i):
 584     " Find end of inset, where lines[i] is included."
 585     return find_end_of(lines, i, "\\begin_inset", "\\end_inset")
 586
 587
 588 def find_end_of_layout(lines, i):
 589     " Find end of layout, where lines[i] is included."
 590     return find_end_of(lines, i, "\\begin_layout", "\\end_layout")
 591
 592
 593 def is_in_inset(lines, i, inset, default=(-1,-1)):
 594     """
 595     Check if line i is in an inset of the given type.
 596     If so, return starting and ending lines, otherwise `default`.
 597     Example:
 598       is_in_inset(document.body, i, "\\begin_inset Tabular")
 599     returns (-1,-1) if `i` is not within a "Tabular" inset (i.e. a table).
 600     If it is, then it returns the line on which the table begins and the one
 601     on which it ends.
 602     Note that this pair will evaulate to boolean True, so (with the optional
 603     default value set to False)
 604       if is_in_inset(..., default=False):
 605     will do what you expect.
 606     """
 607     start = find_token_backwards(lines, inset, i)
 608     if start == -1:
 609       return default
 610     end = find_end_of_inset(lines, start)
 611     if end < i: # this includes the notfound case.
 612       return default
 613     return (start, end)
 614
 615
 616 def get_containing_inset(lines, i):
 617   '''
 618   Finds out what kind of inset line i is within. Returns a
 619   list containing (i) what follows \begin_inset on the line
 620   on which the inset begins, plus the starting and ending line.
 621   Returns False on any kind of error or if it isn't in an inset.
 622   '''
 623   j = i
 624   while True:
 625       stins = find_token_backwards(lines, "\\begin_inset", j)
 626       if stins == -1:
 627           return False
 628       endins = find_end_of_inset(lines, stins)
 629       if endins > j:
 630           break
 631       j = stins - 1
 632
 633   if endins < i:
 634       return False
 635
 636   inset = get_value(lines, "\\begin_inset", stins)
 637   if inset == "":
 638       # shouldn't happen
 639       return False
 640   return (inset, stins, endins)
 641
 642
 643 def get_containing_layout(lines, i):
 644   '''
 645   Find out what kind of layout line `i` is within.
 646   Return a tuple
 647     (layoutname, layoutstart, layoutend, startofcontent)
 648   containing
 649     * layout style/name,
 650     * start line number,
 651     * end line number, and
 652     * number of first paragraph line (after all params).
 653   Return `False` on any kind of error.
 654   '''
 655   j = i
 656   while True:
 657       stlay = find_token_backwards(lines, "\\begin_layout", j)
 658       if stlay == -1:
 659           return False
 660       endlay = find_end_of_layout(lines, stlay)
 661       if endlay > i:
 662           break
 663       j = stlay - 1
 664
 665   if endlay < i:
 666       return False
 667
 668   layoutname = get_value(lines, "\\begin_layout", stlay)
 669   if layoutname == "": # layout style missing
 670       # TODO: What shall we do in this case?
 671       pass
 672       # layoutname == "Standard" # use same fallback as the LyX parser:
 673       # raise ValueError("Missing layout name on line %d"%stlay) # diagnosis
 674       # return False # generic error response
 675   par_params = ["\\noindent", "\\indent", "\\indent-toggle", "\\leftindent",
 676                 "\\start_of_appendix", "\\paragraph_spacing", "\\align",
 677                 "\\labelwidthstring"]
 678   stpar = stlay
 679   while True:
 680       stpar += 1
 681       if lines[stpar].split(' ', 1)[0] not in par_params:
 682           break
 683   return (layoutname, stlay, endlay, stpar)
 684
 685
 686 def count_pars_in_inset(lines, i):
 687   '''
 688   Counts the paragraphs within this inset
 689   '''
 690   ins = get_containing_inset(lines, i)
 691   if ins == -1:
 692       return -1
 693   pars = 0
 694   for j in range(ins[1], ins[2]):
 695       m = re.match(r'\\begin_layout (.*)', lines[j])
 696       if m and get_containing_inset(lines, j)[0] == ins[0]:
 697           pars += 1
 698
 699   return pars
 700
 701
 702 def find_end_of_sequence(lines, i):
 703   '''
 704   Returns the end of a sequence of identical layouts.
 705   '''
 706   lay = get_containing_layout(lines, i)
 707   if lay == False:
 708       return -1
 709   layout = lay[0]
 710   endlay = lay[2]
 711   i = endlay
 712   while True:
 713       m = re.match(r'\\begin_layout (.*)', lines[i])
 714       if m and m.group(1) != layout:
 715           return endlay
 716       elif lines[i] == "\\begin_deeper":
 717           j = find_end_of(lines, i, "\\begin_deeper", "\\end_deeper")
 718           if j != -1:
 719               i = j
 720               endlay = j
 721               continue
 722       if m and m.group(1) == layout:
 723           endlay = find_end_of_layout(lines, i)
 724           i = endlay
 725           continue
 726       if i == len(lines) - 1:
 727           break
 728       i = i + 1
 729
 730   return endlay