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