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]):
  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]]):
  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]]):
  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):
 117   Checks if line i is in an inset of the given type.
 118   If so, returns starting and ending lines. Otherwise,
 119   returns False.
 120   Example:
 121     is_in_inset(document.body, i, "\\begin_inset Tabular")
 122   returns False 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(...):
 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 # Fast search in lists
 160 def find_slice(l, sl, start = 0, stop = None):
 161     """Return position of first occurence of sequence `sl` in list `l`
 162     as a `slice` object.
 163
 164     >>> find_slice([1, 2, 3, 1, 1, 2], (1, 2))
 165     slice(0, 2, None)
 166
 167     The return value can be used to delete or substitute the sub-list:
 168
 169     >>> l = [1, 0, 1, 1, 1, 2]
 170     >>> s = find_slice(l, [0, 1, 1])
 171     >>> del(l[s]); l
 172     [1, 1, 2]
 173     >>> s = find_slice(l, (1, 2))
 174     >>> l[s] = [3]; l
 175     [1, 3]
 176
 177     The start argument works similar to list.index()
 178
 179     >>> find_slice([1, 2, 3, 1, 1 ,2], (1, 2), start = 1)
 180     slice(4, 6, None)
 181
 182     Use the `stop` attribute of the returned `slice` to test for success:
 183
 184     >>> s1 = find_slice([2, 3, 1], (3, 1))
 185     >>> s2 = find_slice([2, 3, 1], (2, 1))
 186     >>> if s1.stop and not s2.stop:
 187     ...     print "wow"
 188     wow
 189     """
 190     stop = stop or len(l)
 191     N = len(sl) # lenght of sub-list
 192     try:
 193         while True:
 194             for j, value in enumerate(sl):
 195                 i = l.index(value, start, stop)
 196                 if j and i != start:
 197                     start = i-j
 198                     break
 199                 start = i +1
 200             else:
 201                 return slice(i+1-N, i+1)
 202     except ValueError: # sub list `sl` not found
 203         return slice(0, 0)
 204
 205
 206 # Utilities for one line
 207 def check_token(line, token):
 208     """ check_token(line, token) -> bool
 209
 210     Return True if token is present in line and is the first element
 211     else returns False.
 212
 213     Deprecated. Use line.startswith(token).
 214     """
 215
 216     return line.startswith(token)
 217
 218
 219 def is_nonempty_line(line):
 220     """ is_nonempty_line(line) -> bool
 221
 222     Return False if line is either empty or it has only whitespaces,
 223     else return True."""
 224     return bool(line.strip())
 225
 226
 227 # Utilities for a list of lines
 228 def find_token(lines, token, start, end = 0, ignorews = False):
 229     """ find_token(lines, token, start[[, end], ignorews]) -> int
 230
 231     Return the lowest line where token is found, and is the first
 232     element, in lines[start, end].
 233
 234     If ignorews is True (default is False), then differences in
 235     whitespace are ignored, except that there must be no extra
 236     whitespace following token itself.
 237
 238     Return -1 on failure."""
 239
 240     if end == 0 or end > len(lines):
 241         end = len(lines)
 242     m = len(token)
 243     for i in range(start, end):
 244         if ignorews:
 245             x = lines[i].split()
 246             y = token.split()
 247             if len(x) < len(y):
 248                 continue
 249             if x[:len(y)] == y:
 250                 return i
 251         else:
 252             if lines[i][:m] == token:
 253                 return i
 254     return -1
 255
 256
 257 def find_token_exact(lines, token, start, end = 0):
 258     return find_token(lines, token, start, end, True)
 259
 260
 261 def find_tokens(lines, tokens, start, end = 0, ignorews = False):
 262     """ find_tokens(lines, tokens, start[[, end], ignorews]) -> int
 263
 264     Return the lowest line where one token in tokens is found, and is
 265     the first element, in lines[start, end].
 266
 267     Return -1 on failure."""
 268     if end == 0 or end > len(lines):
 269         end = len(lines)
 270
 271     for i in range(start, end):
 272         for token in tokens:
 273             if ignorews:
 274                 x = lines[i].split()
 275                 y = token.split()
 276                 if len(x) < len(y):
 277                     continue
 278                 if x[:len(y)] == y:
 279                     return i
 280             else:
 281                 if lines[i][:len(token)] == token:
 282                     return i
 283     return -1
 284
 285
 286 def find_tokens_exact(lines, tokens, start, end = 0):
 287     return find_tokens(lines, tokens, start, end, True)
 288
 289
 290 def find_re(lines, rexp, start, end = 0):
 291     """ find_token_re(lines, rexp, start[, end]) -> int
 292
 293     Return the lowest line where rexp, a regular expression, is found
 294     in lines[start, end].
 295
 296     Return -1 on failure."""
 297
 298     if end == 0 or end > len(lines):
 299         end = len(lines)
 300     for i in range(start, end):
 301         if rexp.match(lines[i]):
 302                 return i
 303     return -1
 304
 305
 306 def find_token_backwards(lines, token, start):
 307     """ find_token_backwards(lines, token, start) -> int
 308
 309     Return the highest line where token is found, and is the first
 310     element, in lines[start, end].
 311
 312     Return -1 on failure."""
 313     m = len(token)
 314     for i in range(start, -1, -1):
 315         line = lines[i]
 316         if line[:m] == token:
 317             return i
 318     return -1
 319
 320
 321 def find_tokens_backwards(lines, tokens, start):
 322     """ find_tokens_backwards(lines, token, start) -> int
 323
 324     Return the highest line where token is found, and is the first
 325     element, in lines[end, start].
 326
 327     Return -1 on failure."""
 328     for i in range(start, -1, -1):
 329         line = lines[i]
 330         for token in tokens:
 331             if line[:len(token)] == token:
 332                 return i
 333     return -1
 334
 335
 336 def get_value(lines, token, start, end = 0, default = ""):
 337     """ get_value(lines, token, start[[, end], default]) -> string
 338
 339     Find the next line that looks like:
 340       token followed by other stuff
 341     Returns "followed by other stuff" with leading and trailing
 342     whitespace removed.
 343     """
 344
 345     i = find_token_exact(lines, token, start, end)
 346     if i == -1:
 347         return default
 348     l = lines[i].split(None, 1)
 349     if len(l) > 1:
 350         return l[1].strip()
 351     return default
 352
 353
 354 def get_quoted_value(lines, token, start, end = 0, default = ""):
 355     """ get_quoted_value(lines, token, start[[, end], default]) -> string
 356
 357     Find the next line that looks like:
 358       token "followed by other stuff"
 359     Returns "followed by other stuff" with leading and trailing
 360     whitespace and quotes removed. If there are no quotes, that is OK too.
 361     So use get_value to preserve possible quotes, this one to remove them,
 362     if they are there.
 363     Note that we will NOT strip quotes from default!
 364     """
 365     val = get_value(lines, token, start, end, "")
 366     if not val:
 367       return default
 368     return val.strip('"')
 369
 370
 371 def get_bool_value(lines, token, start, end = 0, default = None):
 372     """ get_value(lines, token, start[[, end], default]) -> string
 373
 374     Find the next line that looks like:
 375       token bool_value
 376
 377     Returns True if bool_value is 1 or true and
 378     False if bool_value is 0 or false
 379     """
 380
 381     val = get_quoted_value(lines, token, start, end, "")
 382
 383     if val == "1" or val == "true":
 384         return True
 385     if val == "0" or val == "false":
 386         return False
 387     return default
 388
 389
 390 def get_option_value(line, option):
 391     rx = option + '\s*=\s*"([^"]+)"'
 392     rx = re.compile(rx)
 393     m = rx.search(line)
 394     if not m:
 395       return ""
 396     return m.group(1)
 397
 398
 399 def set_option_value(line, option, value):
 400     rx = '(' + option + '\s*=\s*")[^"]+"'
 401     rx = re.compile(rx)
 402     m = rx.search(line)
 403     if not m:
 404         return line
 405     return re.sub(rx, '\g<1>' + value + '"', line)
 406
 407
 408 def del_token(lines, token, start, end = 0):
 409     """ del_token(lines, token, start, end) -> int
 410
 411     Find the first line in lines where token is the first element
 412     and delete that line. Returns True if we deleted a line, False
 413     if we did not."""
 414
 415     k = find_token_exact(lines, token, start, end)
 416     if k == -1:
 417         return False
 418     del lines[k]
 419     return True
 420
 421
 422 def find_beginning_of(lines, i, start_token, end_token):
 423     count = 1
 424     while i > 0:
 425         i = find_tokens_backwards(lines, [start_token, end_token], i-1)
 426         if i == -1:
 427             return -1
 428         if check_token(lines[i], end_token):
 429             count = count+1
 430         else:
 431             count = count-1
 432         if count == 0:
 433             return i
 434     return -1
 435
 436
 437 def find_end_of(lines, i, start_token, end_token):
 438     count = 1
 439     n = len(lines)
 440     while i < n:
 441         i = find_tokens(lines, [end_token, start_token], i+1)
 442         if i == -1:
 443             return -1
 444         if check_token(lines[i], start_token):
 445             count = count+1
 446         else:
 447             count = count-1
 448         if count == 0:
 449             return i
 450     return -1
 451
 452
 453 def find_nonempty_line(lines, start, end = 0):
 454     if end == 0:
 455         end = len(lines)
 456     for i in range(start, end):
 457         if is_nonempty_line(lines[i]):
 458             return i
 459     return -1
 460
 461
 462 def find_end_of_inset(lines, i):
 463     " Find end of inset, where lines[i] is included."
 464     return find_end_of(lines, i, "\\begin_inset", "\\end_inset")
 465
 466
 467 def find_end_of_layout(lines, i):
 468     " Find end of layout, where lines[i] is included."
 469     return find_end_of(lines, i, "\\begin_layout", "\\end_layout")
 470
 471
 472 def is_in_inset(lines, i, inset):
 473     '''
 474     Checks if line i is in an inset of the given type.
 475     If so, returns starting and ending lines.
 476     Otherwise, returns False.
 477     Example:
 478       is_in_inset(document.body, i, "\\begin_inset Tabular")
 479     returns False unless i is within a table. If it is, then
 480     it returns the line on which the table begins and the one
 481     on which it ends. Note that this pair will evaulate to
 482     boolean True, so
 483       if is_in_inset(...):
 484     will do what you expect.
 485     '''
 486     defval = (-1, -1)
 487     stins = find_token_backwards(lines, inset, i)
 488     if stins == -1:
 489       return defval
 490     endins = find_end_of_inset(lines, stins)
 491     # note that this includes the notfound case.
 492     if endins < i:
 493       return defval
 494     return (stins, endins)
 495
 496
 497 def get_containing_inset(lines, i):
 498   '''
 499   Finds out what kind of inset line i is within. Returns a
 500   list containing (i) what follows \begin_inset on the line
 501   on which the inset begins, plus the starting and ending line.
 502   Returns False on any kind of error or if it isn't in an inset.
 503   '''
 504   j = i
 505   while True:
 506       stins = find_token_backwards(lines, "\\begin_inset", j)
 507       if stins == -1:
 508           return False
 509       endins = find_end_of_inset(lines, stins)
 510       if endins > j:
 511           break
 512       j = stins - 1
 513
 514   if endins < i:
 515       return False
 516
 517   inset = get_value(lines, "\\begin_inset", stins)
 518   if inset == "":
 519       # shouldn't happen
 520       return False
 521   return (inset, stins, endins)
 522
 523
 524 def get_containing_layout(lines, i):
 525   '''
 526   Finds out what kind of layout line i is within. Returns a
 527   list containing what follows \begin_layout on the line
 528   on which the layout begins, plus the starting and ending line
 529   and the start of the paragraph (after all params). I.e, returns:
 530     (layoutname, layoutstart, layoutend, startofcontent)
 531   Returns False on any kind of error.
 532   '''
 533   j = i
 534   while True:
 535       stlay = find_token_backwards(lines, "\\begin_layout", j)
 536       if stlay == -1:
 537           return False
 538       endlay = find_end_of_layout(lines, stlay)
 539       if endlay > i:
 540           break
 541       j = stlay - 1
 542
 543   if endlay < i:
 544       return False
 545
 546   lay = get_value(lines, "\\begin_layout", stlay)
 547   if lay == "":
 548       # shouldn't happen
 549       return False
 550   par_params = ["\\noindent", "\\indent", "\\indent-toggle", "\\leftindent",
 551                 "\\start_of_appendix", "\\paragraph_spacing", "\\align",
 552                 "\\labelwidthstring"]
 553   stpar = stlay
 554   while True:
 555       stpar += 1
 556       if lines[stpar].split(' ', 1)[0] not in par_params:
 557           break
 558   return (lay, stlay, endlay, stpar)
 559
 560
 561 def count_pars_in_inset(lines, i):
 562   '''
 563   Counts the paragraphs within this inset
 564   '''
 565   ins = get_containing_inset(lines, i)
 566   if ins == -1:
 567       return -1
 568   pars = 0
 569   for j in range(ins[1], ins[2]):
 570       m = re.match(r'\\begin_layout (.*)', lines[j])
 571       if m and get_containing_inset(lines, j)[0] == ins[0]:
 572           pars += 1
 573
 574   return pars
 575
 576
 577 def find_end_of_sequence(lines, i):
 578   '''
 579   Returns the end of a sequence of identical layouts.
 580   '''
 581   lay = get_containing_layout(lines, i)
 582   if lay == False:
 583       return -1
 584   layout = lay[0]
 585   endlay = lay[2]
 586   i = endlay
 587   while True:
 588       m = re.match(r'\\begin_layout (.*)', lines[i])
 589       if m and m.group(1) != layout:
 590           return endlay
 591       elif lines[i] == "\\begin_deeper":
 592           j = find_end_of(lines, i, "\\begin_deeper", "\\end_deeper")
 593           if j != -1:
 594               i = j
 595               endlay = j
 596               continue
 597       if m and m.group(1) == layout:
 598           endlay = find_end_of_layout(lines, i)
 599           i = endlay
 600           continue
 601       if i == len(lines) - 1:
 602           break
 603       i = i + 1
 604
 605   return endlay