Mercurial > traipse_dev

comparison upmana/mercurial/patch.py @ 135:dcf4fbe09b70 beta

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Traipse Beta 'OpenRPG' {091010-00} Traipse is a distribution of OpenRPG that is designed to be easy to setup and go. Traipse also makes it easy for developers to work on code without fear of sacrifice. 'Ornery-Orc' continues the trend of 'Grumpy' and adds fixes to the code. 'Ornery-Orc's main goal is to offer more advanced features and enhance the productivity of the user. Update Summary (Beta) Added Bookmarks Fix to Remote Admin Commands Minor fix to text based Server Fix to Pretty Print, from Core Fix to Splitter Nodes not being created Fix to massive amounts of images loading, from Core Added 'boot' command to remote admin Added confirmation window for sent nodes Minor changes to allow for portability to an OpenSUSE linux OS Miniatures Layer pop up box allows users to turn off Mini labels, from FlexiRPG Zoom Mouse plugin added Images added to Plugin UI Switching to Element Tree Map efficiency, from FlexiRPG Added Status Bar to Update Manager default_manifest.xml renamed to default_upmana.xml Cleaner clode for saved repositories New TrueDebug Class in orpg_log (See documentation for usage) Mercurial's hgweb folder is ported to upmana **Pretty important update that can help remove thousands of dead children from your gametree. **Children, <forms />, <group_atts />, <horizontal />, <cols />, <rows />, <height />, etc... are all tags now. Check your gametree and look for dead children!! **New Gamtree Recusion method, mapping, and context sensitivity. !!Alpha - Watch out for infinite loops!!
author sirebral
date Tue, 10 Nov 2009 14:11:28 -0600
parents
children
comparison
equal deleted inserted replaced
101:394ebb3b6a0f 135:dcf4fbe09b70
1 # patch.py - patch file parsing routines
2 #
3 # Copyright 2006 Brendan Cully <brendan@kublai.com>
4 # Copyright 2007 Chris Mason <chris.mason@oracle.com>
5 #
6 # This software may be used and distributed according to the terms of the
7 # GNU General Public License version 2, incorporated herein by reference.
8
9 from i18n import _
10 from node import hex, nullid, short
11 import base85, cmdutil, mdiff, util, diffhelpers, copies
12 import cStringIO, email.Parser, os, re, math
13 import sys, tempfile, zlib
14
15 gitre = re.compile('diff --git a/(.*) b/(.*)')
16
17 class PatchError(Exception):
18 pass
19
20 class NoHunks(PatchError):
21 pass
22
23 # helper functions
24
25 def copyfile(src, dst, basedir):
26 abssrc, absdst = [util.canonpath(basedir, basedir, x) for x in [src, dst]]
27 if os.path.exists(absdst):
28 raise util.Abort(_("cannot create %s: destination already exists") %
29 dst)
30
31 dstdir = os.path.dirname(absdst)
32 if dstdir and not os.path.isdir(dstdir):
33 try:
34 os.makedirs(dstdir)
35 except IOError:
36 raise util.Abort(
37 _("cannot create %s: unable to create destination directory")
38 % dst)
39
40 util.copyfile(abssrc, absdst)
41
42 # public functions
43
44 def extract(ui, fileobj):
45 '''extract patch from data read from fileobj.
46
47 patch can be a normal patch or contained in an email message.
48
49 return tuple (filename, message, user, date, node, p1, p2).
50 Any item in the returned tuple can be None. If filename is None,
51 fileobj did not contain a patch. Caller must unlink filename when done.'''
52
53 # attempt to detect the start of a patch
54 # (this heuristic is borrowed from quilt)
55 diffre = re.compile(r'^(?:Index:[ \t]|diff[ \t]|RCS file: |'
56 r'retrieving revision [0-9]+(\.[0-9]+)*$|'
57 r'(---|\*\*\*)[ \t])', re.MULTILINE)
58
59 fd, tmpname = tempfile.mkstemp(prefix='hg-patch-')
60 tmpfp = os.fdopen(fd, 'w')
61 try:
62 msg = email.Parser.Parser().parse(fileobj)
63
64 subject = msg['Subject']
65 user = msg['From']
66 gitsendmail = 'git-send-email' in msg.get('X-Mailer', '')
67 # should try to parse msg['Date']
68 date = None
69 nodeid = None
70 branch = None
71 parents = []
72
73 if subject:
74 if subject.startswith('[PATCH'):
75 pend = subject.find(']')
76 if pend >= 0:
77 subject = subject[pend+1:].lstrip()
78 subject = subject.replace('\n\t', ' ')
79 ui.debug('Subject: %s\n' % subject)
80 if user:
81 ui.debug('From: %s\n' % user)
82 diffs_seen = 0
83 ok_types = ('text/plain', 'text/x-diff', 'text/x-patch')
84 message = ''
85 for part in msg.walk():
86 content_type = part.get_content_type()
87 ui.debug('Content-Type: %s\n' % content_type)
88 if content_type not in ok_types:
89 continue
90 payload = part.get_payload(decode=True)
91 m = diffre.search(payload)
92 if m:
93 hgpatch = False
94 ignoretext = False
95
96 ui.debug(_('found patch at byte %d\n') % m.start(0))
97 diffs_seen += 1
98 cfp = cStringIO.StringIO()
99 for line in payload[:m.start(0)].splitlines():
100 if line.startswith('# HG changeset patch'):
101 ui.debug(_('patch generated by hg export\n'))
102 hgpatch = True
103 # drop earlier commit message content
104 cfp.seek(0)
105 cfp.truncate()
106 subject = None
107 elif hgpatch:
108 if line.startswith('# User '):
109 user = line[7:]
110 ui.debug('From: %s\n' % user)
111 elif line.startswith("# Date "):
112 date = line[7:]
113 elif line.startswith("# Branch "):
114 branch = line[9:]
115 elif line.startswith("# Node ID "):
116 nodeid = line[10:]
117 elif line.startswith("# Parent "):
118 parents.append(line[10:])
119 elif line == '---' and gitsendmail:
120 ignoretext = True
121 if not line.startswith('# ') and not ignoretext:
122 cfp.write(line)
123 cfp.write('\n')
124 message = cfp.getvalue()
125 if tmpfp:
126 tmpfp.write(payload)
127 if not payload.endswith('\n'):
128 tmpfp.write('\n')
129 elif not diffs_seen and message and content_type == 'text/plain':
130 message += '\n' + payload
131 except:
132 tmpfp.close()
133 os.unlink(tmpname)
134 raise
135
136 if subject and not message.startswith(subject):
137 message = '%s\n%s' % (subject, message)
138 tmpfp.close()
139 if not diffs_seen:
140 os.unlink(tmpname)
141 return None, message, user, date, branch, None, None, None
142 p1 = parents and parents.pop(0) or None
143 p2 = parents and parents.pop(0) or None
144 return tmpname, message, user, date, branch, nodeid, p1, p2
145
146 GP_PATCH = 1 << 0 # we have to run patch
147 GP_FILTER = 1 << 1 # there's some copy/rename operation
148 GP_BINARY = 1 << 2 # there's a binary patch
149
150 class patchmeta(object):
151 """Patched file metadata
152
153 'op' is the performed operation within ADD, DELETE, RENAME, MODIFY
154 or COPY. 'path' is patched file path. 'oldpath' is set to the
155 origin file when 'op' is either COPY or RENAME, None otherwise. If
156 file mode is changed, 'mode' is a tuple (islink, isexec) where
157 'islink' is True if the file is a symlink and 'isexec' is True if
158 the file is executable. Otherwise, 'mode' is None.
159 """
160 def __init__(self, path):
161 self.path = path
162 self.oldpath = None
163 self.mode = None
164 self.op = 'MODIFY'
165 self.lineno = 0
166 self.binary = False
167
168 def setmode(self, mode):
169 islink = mode & 020000
170 isexec = mode & 0100
171 self.mode = (islink, isexec)
172
173 def readgitpatch(lr):
174 """extract git-style metadata about patches from <patchname>"""
175
176 # Filter patch for git information
177 gp = None
178 gitpatches = []
179 # Can have a git patch with only metadata, causing patch to complain
180 dopatch = 0
181
182 lineno = 0
183 for line in lr:
184 lineno += 1
185 if line.startswith('diff --git'):
186 m = gitre.match(line)
187 if m:
188 if gp:
189 gitpatches.append(gp)
190 src, dst = m.group(1, 2)
191 gp = patchmeta(dst)
192 gp.lineno = lineno
193 elif gp:
194 if line.startswith('--- '):
195 if gp.op in ('COPY', 'RENAME'):
196 dopatch |= GP_FILTER
197 gitpatches.append(gp)
198 gp = None
199 dopatch |= GP_PATCH
200 continue
201 if line.startswith('rename from '):
202 gp.op = 'RENAME'
203 gp.oldpath = line[12:].rstrip()
204 elif line.startswith('rename to '):
205 gp.path = line[10:].rstrip()
206 elif line.startswith('copy from '):
207 gp.op = 'COPY'
208 gp.oldpath = line[10:].rstrip()
209 elif line.startswith('copy to '):
210 gp.path = line[8:].rstrip()
211 elif line.startswith('deleted file'):
212 gp.op = 'DELETE'
213 # is the deleted file a symlink?
214 gp.setmode(int(line.rstrip()[-6:], 8))
215 elif line.startswith('new file mode '):
216 gp.op = 'ADD'
217 gp.setmode(int(line.rstrip()[-6:], 8))
218 elif line.startswith('new mode '):
219 gp.setmode(int(line.rstrip()[-6:], 8))
220 elif line.startswith('GIT binary patch'):
221 dopatch |= GP_BINARY
222 gp.binary = True
223 if gp:
224 gitpatches.append(gp)
225
226 if not gitpatches:
227 dopatch = GP_PATCH
228
229 return (dopatch, gitpatches)
230
231 class linereader(object):
232 # simple class to allow pushing lines back into the input stream
233 def __init__(self, fp, textmode=False):
234 self.fp = fp
235 self.buf = []
236 self.textmode = textmode
237
238 def push(self, line):
239 if line is not None:
240 self.buf.append(line)
241
242 def readline(self):
243 if self.buf:
244 l = self.buf[0]
245 del self.buf[0]
246 return l
247 l = self.fp.readline()
248 if self.textmode and l.endswith('\r\n'):
249 l = l[:-2] + '\n'
250 return l
251
252 def __iter__(self):
253 while 1:
254 l = self.readline()
255 if not l:
256 break
257 yield l
258
259 # @@ -start,len +start,len @@ or @@ -start +start @@ if len is 1
260 unidesc = re.compile('@@ -(\d+)(,(\d+))? \+(\d+)(,(\d+))? @@')
261 contextdesc = re.compile('(---|\*\*\*) (\d+)(,(\d+))? (---|\*\*\*)')
262
263 class patchfile(object):
264 def __init__(self, ui, fname, opener, missing=False, eol=None):
265 self.fname = fname
266 self.eol = eol
267 self.opener = opener
268 self.ui = ui
269 self.lines = []
270 self.exists = False
271 self.missing = missing
272 if not missing:
273 try:
274 self.lines = self.readlines(fname)
275 self.exists = True
276 except IOError:
277 pass
278 else:
279 self.ui.warn(_("unable to find '%s' for patching\n") % self.fname)
280
281 self.hash = {}
282 self.dirty = 0
283 self.offset = 0
284 self.rej = []
285 self.fileprinted = False
286 self.printfile(False)
287 self.hunks = 0
288
289 def readlines(self, fname):
290 fp = self.opener(fname, 'r')
291 try:
292 return list(linereader(fp, self.eol is not None))
293 finally:
294 fp.close()
295
296 def writelines(self, fname, lines):
297 fp = self.opener(fname, 'w')
298 try:
299 if self.eol and self.eol != '\n':
300 for l in lines:
301 if l and l[-1] == '\n':
302 l = l[:-1] + self.eol
303 fp.write(l)
304 else:
305 fp.writelines(lines)
306 finally:
307 fp.close()
308
309 def unlink(self, fname):
310 os.unlink(fname)
311
312 def printfile(self, warn):
313 if self.fileprinted:
314 return
315 if warn or self.ui.verbose:
316 self.fileprinted = True
317 s = _("patching file %s\n") % self.fname
318 if warn:
319 self.ui.warn(s)
320 else:
321 self.ui.note(s)
322
323
324 def findlines(self, l, linenum):
325 # looks through the hash and finds candidate lines. The
326 # result is a list of line numbers sorted based on distance
327 # from linenum
328 def sorter(a, b):
329 vala = abs(a - linenum)
330 valb = abs(b - linenum)
331 return cmp(vala, valb)
332
333 try:
334 cand = self.hash[l]
335 except:
336 return []
337
338 if len(cand) > 1:
339 # resort our list of potentials forward then back.
340 cand.sort(sorter)
341 return cand
342
343 def hashlines(self):
344 self.hash = {}
345 for x, s in enumerate(self.lines):
346 self.hash.setdefault(s, []).append(x)
347
348 def write_rej(self):
349 # our rejects are a little different from patch(1). This always
350 # creates rejects in the same form as the original patch. A file
351 # header is inserted so that you can run the reject through patch again
352 # without having to type the filename.
353
354 if not self.rej:
355 return
356
357 fname = self.fname + ".rej"
358 self.ui.warn(
359 _("%d out of %d hunks FAILED -- saving rejects to file %s\n") %
360 (len(self.rej), self.hunks, fname))
361
362 def rejlines():
363 base = os.path.basename(self.fname)
364 yield "--- %s\n+++ %s\n" % (base, base)
365 for x in self.rej:
366 for l in x.hunk:
367 yield l
368 if l[-1] != '\n':
369 yield "\n\ No newline at end of file\n"
370
371 self.writelines(fname, rejlines())
372
373 def write(self, dest=None):
374 if not self.dirty:
375 return
376 if not dest:
377 dest = self.fname
378 self.writelines(dest, self.lines)
379
380 def close(self):
381 self.write()
382 self.write_rej()
383
384 def apply(self, h, reverse):
385 if not h.complete():
386 raise PatchError(_("bad hunk #%d %s (%d %d %d %d)") %
387 (h.number, h.desc, len(h.a), h.lena, len(h.b),
388 h.lenb))
389
390 self.hunks += 1
391 if reverse:
392 h.reverse()
393
394 if self.missing:
395 self.rej.append(h)
396 return -1
397
398 if self.exists and h.createfile():
399 self.ui.warn(_("file %s already exists\n") % self.fname)
400 self.rej.append(h)
401 return -1
402
403 if isinstance(h, githunk):
404 if h.rmfile():
405 self.unlink(self.fname)
406 else:
407 self.lines[:] = h.new()
408 self.offset += len(h.new())
409 self.dirty = 1
410 return 0
411
412 # fast case first, no offsets, no fuzz
413 old = h.old()
414 # patch starts counting at 1 unless we are adding the file
415 if h.starta == 0:
416 start = 0
417 else:
418 start = h.starta + self.offset - 1
419 orig_start = start
420 if diffhelpers.testhunk(old, self.lines, start) == 0:
421 if h.rmfile():
422 self.unlink(self.fname)
423 else:
424 self.lines[start : start + h.lena] = h.new()
425 self.offset += h.lenb - h.lena
426 self.dirty = 1
427 return 0
428
429 # ok, we couldn't match the hunk. Lets look for offsets and fuzz it
430 self.hashlines()
431 if h.hunk[-1][0] != ' ':
432 # if the hunk tried to put something at the bottom of the file
433 # override the start line and use eof here
434 search_start = len(self.lines)
435 else:
436 search_start = orig_start
437
438 for fuzzlen in xrange(3):
439 for toponly in [ True, False ]:
440 old = h.old(fuzzlen, toponly)
441
442 cand = self.findlines(old[0][1:], search_start)
443 for l in cand:
444 if diffhelpers.testhunk(old, self.lines, l) == 0:
445 newlines = h.new(fuzzlen, toponly)
446 self.lines[l : l + len(old)] = newlines
447 self.offset += len(newlines) - len(old)
448 self.dirty = 1
449 if fuzzlen:
450 fuzzstr = "with fuzz %d " % fuzzlen
451 f = self.ui.warn
452 self.printfile(True)
453 else:
454 fuzzstr = ""
455 f = self.ui.note
456 offset = l - orig_start - fuzzlen
457 if offset == 1:
458 msg = _("Hunk #%d succeeded at %d %s"
459 "(offset %d line).\n")
460 else:
461 msg = _("Hunk #%d succeeded at %d %s"
462 "(offset %d lines).\n")
463 f(msg % (h.number, l+1, fuzzstr, offset))
464 return fuzzlen
465 self.printfile(True)
466 self.ui.warn(_("Hunk #%d FAILED at %d\n") % (h.number, orig_start))
467 self.rej.append(h)
468 return -1
469
470 class hunk(object):
471 def __init__(self, desc, num, lr, context, create=False, remove=False):
472 self.number = num
473 self.desc = desc
474 self.hunk = [ desc ]
475 self.a = []
476 self.b = []
477 if context:
478 self.read_context_hunk(lr)
479 else:
480 self.read_unified_hunk(lr)
481 self.create = create
482 self.remove = remove and not create
483
484 def read_unified_hunk(self, lr):
485 m = unidesc.match(self.desc)
486 if not m:
487 raise PatchError(_("bad hunk #%d") % self.number)
488 self.starta, foo, self.lena, self.startb, foo2, self.lenb = m.groups()
489 if self.lena is None:
490 self.lena = 1
491 else:
492 self.lena = int(self.lena)
493 if self.lenb is None:
494 self.lenb = 1
495 else:
496 self.lenb = int(self.lenb)
497 self.starta = int(self.starta)
498 self.startb = int(self.startb)
499 diffhelpers.addlines(lr, self.hunk, self.lena, self.lenb, self.a, self.b)
500 # if we hit eof before finishing out the hunk, the last line will
501 # be zero length. Lets try to fix it up.
502 while len(self.hunk[-1]) == 0:
503 del self.hunk[-1]
504 del self.a[-1]
505 del self.b[-1]
506 self.lena -= 1
507 self.lenb -= 1
508
509 def read_context_hunk(self, lr):
510 self.desc = lr.readline()
511 m = contextdesc.match(self.desc)
512 if not m:
513 raise PatchError(_("bad hunk #%d") % self.number)
514 foo, self.starta, foo2, aend, foo3 = m.groups()
515 self.starta = int(self.starta)
516 if aend is None:
517 aend = self.starta
518 self.lena = int(aend) - self.starta
519 if self.starta:
520 self.lena += 1
521 for x in xrange(self.lena):
522 l = lr.readline()
523 if l.startswith('---'):
524 lr.push(l)
525 break
526 s = l[2:]
527 if l.startswith('- ') or l.startswith('! '):
528 u = '-' + s
529 elif l.startswith(' '):
530 u = ' ' + s
531 else:
532 raise PatchError(_("bad hunk #%d old text line %d") %
533 (self.number, x))
534 self.a.append(u)
535 self.hunk.append(u)
536
537 l = lr.readline()
538 if l.startswith('\ '):
539 s = self.a[-1][:-1]
540 self.a[-1] = s
541 self.hunk[-1] = s
542 l = lr.readline()
543 m = contextdesc.match(l)
544 if not m:
545 raise PatchError(_("bad hunk #%d") % self.number)
546 foo, self.startb, foo2, bend, foo3 = m.groups()
547 self.startb = int(self.startb)
548 if bend is None:
549 bend = self.startb
550 self.lenb = int(bend) - self.startb
551 if self.startb:
552 self.lenb += 1
553 hunki = 1
554 for x in xrange(self.lenb):
555 l = lr.readline()
556 if l.startswith('\ '):
557 s = self.b[-1][:-1]
558 self.b[-1] = s
559 self.hunk[hunki-1] = s
560 continue
561 if not l:
562 lr.push(l)
563 break
564 s = l[2:]
565 if l.startswith('+ ') or l.startswith('! '):
566 u = '+' + s
567 elif l.startswith(' '):
568 u = ' ' + s
569 elif len(self.b) == 0:
570 # this can happen when the hunk does not add any lines
571 lr.push(l)
572 break
573 else:
574 raise PatchError(_("bad hunk #%d old text line %d") %
575 (self.number, x))
576 self.b.append(s)
577 while True:
578 if hunki >= len(self.hunk):
579 h = ""
580 else:
581 h = self.hunk[hunki]
582 hunki += 1
583 if h == u:
584 break
585 elif h.startswith('-'):
586 continue
587 else:
588 self.hunk.insert(hunki-1, u)
589 break
590
591 if not self.a:
592 # this happens when lines were only added to the hunk
593 for x in self.hunk:
594 if x.startswith('-') or x.startswith(' '):
595 self.a.append(x)
596 if not self.b:
597 # this happens when lines were only deleted from the hunk
598 for x in self.hunk:
599 if x.startswith('+') or x.startswith(' '):
600 self.b.append(x[1:])
601 # @@ -start,len +start,len @@
602 self.desc = "@@ -%d,%d +%d,%d @@\n" % (self.starta, self.lena,
603 self.startb, self.lenb)
604 self.hunk[0] = self.desc
605
606 def reverse(self):
607 self.create, self.remove = self.remove, self.create
608 origlena = self.lena
609 origstarta = self.starta
610 self.lena = self.lenb
611 self.starta = self.startb
612 self.lenb = origlena
613 self.startb = origstarta
614 self.a = []
615 self.b = []
616 # self.hunk[0] is the @@ description
617 for x in xrange(1, len(self.hunk)):
618 o = self.hunk[x]
619 if o.startswith('-'):
620 n = '+' + o[1:]
621 self.b.append(o[1:])
622 elif o.startswith('+'):
623 n = '-' + o[1:]
624 self.a.append(n)
625 else:
626 n = o
627 self.b.append(o[1:])
628 self.a.append(o)
629 self.hunk[x] = o
630
631 def fix_newline(self):
632 diffhelpers.fix_newline(self.hunk, self.a, self.b)
633
634 def complete(self):
635 return len(self.a) == self.lena and len(self.b) == self.lenb
636
637 def createfile(self):
638 return self.starta == 0 and self.lena == 0 and self.create
639
640 def rmfile(self):
641 return self.startb == 0 and self.lenb == 0 and self.remove
642
643 def fuzzit(self, l, fuzz, toponly):
644 # this removes context lines from the top and bottom of list 'l'. It
645 # checks the hunk to make sure only context lines are removed, and then
646 # returns a new shortened list of lines.
647 fuzz = min(fuzz, len(l)-1)
648 if fuzz:
649 top = 0
650 bot = 0
651 hlen = len(self.hunk)
652 for x in xrange(hlen-1):
653 # the hunk starts with the @@ line, so use x+1
654 if self.hunk[x+1][0] == ' ':
655 top += 1
656 else:
657 break
658 if not toponly:
659 for x in xrange(hlen-1):
660 if self.hunk[hlen-bot-1][0] == ' ':
661 bot += 1
662 else:
663 break
664
665 # top and bot now count context in the hunk
666 # adjust them if either one is short
667 context = max(top, bot, 3)
668 if bot < context:
669 bot = max(0, fuzz - (context - bot))
670 else:
671 bot = min(fuzz, bot)
672 if top < context:
673 top = max(0, fuzz - (context - top))
674 else:
675 top = min(fuzz, top)
676
677 return l[top:len(l)-bot]
678 return l
679
680 def old(self, fuzz=0, toponly=False):
681 return self.fuzzit(self.a, fuzz, toponly)
682
683 def newctrl(self):
684 res = []
685 for x in self.hunk:
686 c = x[0]
687 if c == ' ' or c == '+':
688 res.append(x)
689 return res
690
691 def new(self, fuzz=0, toponly=False):
692 return self.fuzzit(self.b, fuzz, toponly)
693
694 class githunk(object):
695 """A git hunk"""
696 def __init__(self, gitpatch):
697 self.gitpatch = gitpatch
698 self.text = None
699 self.hunk = []
700
701 def createfile(self):
702 return self.gitpatch.op in ('ADD', 'RENAME', 'COPY')
703
704 def rmfile(self):
705 return self.gitpatch.op == 'DELETE'
706
707 def complete(self):
708 return self.text is not None
709
710 def new(self):
711 return [self.text]
712
713 class binhunk(githunk):
714 'A binary patch file. Only understands literals so far.'
715 def __init__(self, gitpatch):
716 super(binhunk, self).__init__(gitpatch)
717 self.hunk = ['GIT binary patch\n']
718
719 def extract(self, lr):
720 line = lr.readline()
721 self.hunk.append(line)
722 while line and not line.startswith('literal '):
723 line = lr.readline()
724 self.hunk.append(line)
725 if not line:
726 raise PatchError(_('could not extract binary patch'))
727 size = int(line[8:].rstrip())
728 dec = []
729 line = lr.readline()
730 self.hunk.append(line)
731 while len(line) > 1:
732 l = line[0]
733 if l <= 'Z' and l >= 'A':
734 l = ord(l) - ord('A') + 1
735 else:
736 l = ord(l) - ord('a') + 27
737 dec.append(base85.b85decode(line[1:-1])[:l])
738 line = lr.readline()
739 self.hunk.append(line)
740 text = zlib.decompress(''.join(dec))
741 if len(text) != size:
742 raise PatchError(_('binary patch is %d bytes, not %d') %
743 len(text), size)
744 self.text = text
745
746 class symlinkhunk(githunk):
747 """A git symlink hunk"""
748 def __init__(self, gitpatch, hunk):
749 super(symlinkhunk, self).__init__(gitpatch)
750 self.hunk = hunk
751
752 def complete(self):
753 return True
754
755 def fix_newline(self):
756 return
757
758 def parsefilename(str):
759 # --- filename \t|space stuff
760 s = str[4:].rstrip('\r\n')
761 i = s.find('\t')
762 if i < 0:
763 i = s.find(' ')
764 if i < 0:
765 return s
766 return s[:i]
767
768 def selectfile(afile_orig, bfile_orig, hunk, strip, reverse):
769 def pathstrip(path, count=1):
770 pathlen = len(path)
771 i = 0
772 if count == 0:
773 return '', path.rstrip()
774 while count > 0:
775 i = path.find('/', i)
776 if i == -1:
777 raise PatchError(_("unable to strip away %d dirs from %s") %
778 (count, path))
779 i += 1
780 # consume '//' in the path
781 while i < pathlen - 1 and path[i] == '/':
782 i += 1
783 count -= 1
784 return path[:i].lstrip(), path[i:].rstrip()
785
786 nulla = afile_orig == "/dev/null"
787 nullb = bfile_orig == "/dev/null"
788 abase, afile = pathstrip(afile_orig, strip)
789 gooda = not nulla and util.lexists(afile)
790 bbase, bfile = pathstrip(bfile_orig, strip)
791 if afile == bfile:
792 goodb = gooda
793 else:
794 goodb = not nullb and os.path.exists(bfile)
795 createfunc = hunk.createfile
796 if reverse:
797 createfunc = hunk.rmfile
798 missing = not goodb and not gooda and not createfunc()
799 # If afile is "a/b/foo" and bfile is "a/b/foo.orig" we assume the
800 # diff is between a file and its backup. In this case, the original
801 # file should be patched (see original mpatch code).
802 isbackup = (abase == bbase and bfile.startswith(afile))
803 fname = None
804 if not missing:
805 if gooda and goodb:
806 fname = isbackup and afile or bfile
807 elif gooda:
808 fname = afile
809
810 if not fname:
811 if not nullb:
812 fname = isbackup and afile or bfile
813 elif not nulla:
814 fname = afile
815 else:
816 raise PatchError(_("undefined source and destination files"))
817
818 return fname, missing
819
820 def scangitpatch(lr, firstline):
821 """
822 Git patches can emit:
823 - rename a to b
824 - change b
825 - copy a to c
826 - change c
827
828 We cannot apply this sequence as-is, the renamed 'a' could not be
829 found for it would have been renamed already. And we cannot copy
830 from 'b' instead because 'b' would have been changed already. So
831 we scan the git patch for copy and rename commands so we can
832 perform the copies ahead of time.
833 """
834 pos = 0
835 try:
836 pos = lr.fp.tell()
837 fp = lr.fp
838 except IOError:
839 fp = cStringIO.StringIO(lr.fp.read())
840 gitlr = linereader(fp, lr.textmode)
841 gitlr.push(firstline)
842 (dopatch, gitpatches) = readgitpatch(gitlr)
843 fp.seek(pos)
844 return dopatch, gitpatches
845
846 def iterhunks(ui, fp, sourcefile=None, textmode=False):
847 """Read a patch and yield the following events:
848 - ("file", afile, bfile, firsthunk): select a new target file.
849 - ("hunk", hunk): a new hunk is ready to be applied, follows a
850 "file" event.
851 - ("git", gitchanges): current diff is in git format, gitchanges
852 maps filenames to gitpatch records. Unique event.
853
854 If textmode is True, input line-endings are normalized to LF.
855 """
856 changed = {}
857 current_hunk = None
858 afile = ""
859 bfile = ""
860 state = None
861 hunknum = 0
862 emitfile = False
863 git = False
864
865 # our states
866 BFILE = 1
867 context = None
868 lr = linereader(fp, textmode)
869 dopatch = True
870 # gitworkdone is True if a git operation (copy, rename, ...) was
871 # performed already for the current file. Useful when the file
872 # section may have no hunk.
873 gitworkdone = False
874
875 while True:
876 newfile = False
877 x = lr.readline()
878 if not x:
879 break
880 if current_hunk:
881 if x.startswith('\ '):
882 current_hunk.fix_newline()
883 yield 'hunk', current_hunk
884 current_hunk = None
885 gitworkdone = False
886 if ((sourcefile or state == BFILE) and ((not context and x[0] == '@') or
887 ((context is not False) and x.startswith('***************')))):
888 try:
889 if context is None and x.startswith('***************'):
890 context = True
891 gpatch = changed.get(bfile)
892 create = afile == '/dev/null' or gpatch and gpatch.op == 'ADD'
893 remove = bfile == '/dev/null' or gpatch and gpatch.op == 'DELETE'
894 current_hunk = hunk(x, hunknum + 1, lr, context, create, remove)
895 if remove:
896 gpatch = changed.get(afile[2:])
897 if gpatch and gpatch.mode[0]:
898 current_hunk = symlinkhunk(gpatch, current_hunk)
899 except PatchError, err:
900 ui.debug(err)
901 current_hunk = None
902 continue
903 hunknum += 1
904 if emitfile:
905 emitfile = False
906 yield 'file', (afile, bfile, current_hunk)
907 elif state == BFILE and x.startswith('GIT binary patch'):
908 current_hunk = binhunk(changed[bfile])
909 hunknum += 1
910 if emitfile:
911 emitfile = False
912 yield 'file', ('a/' + afile, 'b/' + bfile, current_hunk)
913 current_hunk.extract(lr)
914 elif x.startswith('diff --git'):
915 # check for git diff, scanning the whole patch file if needed
916 m = gitre.match(x)
917 if m:
918 afile, bfile = m.group(1, 2)
919 if not git:
920 git = True
921 dopatch, gitpatches = scangitpatch(lr, x)
922 yield 'git', gitpatches
923 for gp in gitpatches:
924 changed[gp.path] = gp
925 # else error?
926 # copy/rename + modify should modify target, not source
927 gp = changed.get(bfile)
928 if gp and gp.op in ('COPY', 'DELETE', 'RENAME', 'ADD'):
929 afile = bfile
930 gitworkdone = True
931 newfile = True
932 elif x.startswith('---'):
933 # check for a unified diff
934 l2 = lr.readline()
935 if not l2.startswith('+++'):
936 lr.push(l2)
937 continue
938 newfile = True
939 context = False
940 afile = parsefilename(x)
941 bfile = parsefilename(l2)
942 elif x.startswith('***'):
943 # check for a context diff
944 l2 = lr.readline()
945 if not l2.startswith('---'):
946 lr.push(l2)
947 continue
948 l3 = lr.readline()
949 lr.push(l3)
950 if not l3.startswith("***************"):
951 lr.push(l2)
952 continue
953 newfile = True
954 context = True
955 afile = parsefilename(x)
956 bfile = parsefilename(l2)
957
958 if newfile:
959 emitfile = True
960 state = BFILE
961 hunknum = 0
962 if current_hunk:
963 if current_hunk.complete():
964 yield 'hunk', current_hunk
965 else:
966 raise PatchError(_("malformed patch %s %s") % (afile,
967 current_hunk.desc))
968
969 if hunknum == 0 and dopatch and not gitworkdone:
970 raise NoHunks
971
972 def applydiff(ui, fp, changed, strip=1, sourcefile=None, reverse=False,
973 eol=None):
974 """
975 Reads a patch from fp and tries to apply it.
976
977 The dict 'changed' is filled in with all of the filenames changed
978 by the patch. Returns 0 for a clean patch, -1 if any rejects were
979 found and 1 if there was any fuzz.
980
981 If 'eol' is None, the patch content and patched file are read in
982 binary mode. Otherwise, line endings are ignored when patching then
983 normalized to 'eol' (usually '\n' or \r\n').
984 """
985 rejects = 0
986 err = 0
987 current_file = None
988 gitpatches = None
989 opener = util.opener(os.getcwd())
990 textmode = eol is not None
991
992 def closefile():
993 if not current_file:
994 return 0
995 current_file.close()
996 return len(current_file.rej)
997
998 for state, values in iterhunks(ui, fp, sourcefile, textmode):
999 if state == 'hunk':
1000 if not current_file:
1001 continue
1002 current_hunk = values
1003 ret = current_file.apply(current_hunk, reverse)
1004 if ret >= 0:
1005 changed.setdefault(current_file.fname, None)
1006 if ret > 0:
1007 err = 1
1008 elif state == 'file':
1009 rejects += closefile()
1010 afile, bfile, first_hunk = values
1011 try:
1012 if sourcefile:
1013 current_file = patchfile(ui, sourcefile, opener, eol=eol)
1014 else:
1015 current_file, missing = selectfile(afile, bfile, first_hunk,
1016 strip, reverse)
1017 current_file = patchfile(ui, current_file, opener, missing, eol)
1018 except PatchError, err:
1019 ui.warn(str(err) + '\n')
1020 current_file, current_hunk = None, None
1021 rejects += 1
1022 continue
1023 elif state == 'git':
1024 gitpatches = values
1025 cwd = os.getcwd()
1026 for gp in gitpatches:
1027 if gp.op in ('COPY', 'RENAME'):
1028 copyfile(gp.oldpath, gp.path, cwd)
1029 changed[gp.path] = gp
1030 else:
1031 raise util.Abort(_('unsupported parser state: %s') % state)
1032
1033 rejects += closefile()
1034
1035 if rejects:
1036 return -1
1037 return err
1038
1039 def diffopts(ui, opts={}, untrusted=False):
1040 def get(key, name=None, getter=ui.configbool):
1041 return (opts.get(key) or
1042 getter('diff', name or key, None, untrusted=untrusted))
1043 return mdiff.diffopts(
1044 text=opts.get('text'),
1045 git=get('git'),
1046 nodates=get('nodates'),
1047 showfunc=get('show_function', 'showfunc'),
1048 ignorews=get('ignore_all_space', 'ignorews'),
1049 ignorewsamount=get('ignore_space_change', 'ignorewsamount'),
1050 ignoreblanklines=get('ignore_blank_lines', 'ignoreblanklines'),
1051 context=get('unified', getter=ui.config))
1052
1053 def updatedir(ui, repo, patches, similarity=0):
1054 '''Update dirstate after patch application according to metadata'''
1055 if not patches:
1056 return
1057 copies = []
1058 removes = set()
1059 cfiles = patches.keys()
1060 cwd = repo.getcwd()
1061 if cwd:
1062 cfiles = [util.pathto(repo.root, cwd, f) for f in patches.keys()]
1063 for f in patches:
1064 gp = patches[f]
1065 if not gp:
1066 continue
1067 if gp.op == 'RENAME':
1068 copies.append((gp.oldpath, gp.path))
1069 removes.add(gp.oldpath)
1070 elif gp.op == 'COPY':
1071 copies.append((gp.oldpath, gp.path))
1072 elif gp.op == 'DELETE':
1073 removes.add(gp.path)
1074 for src, dst in copies:
1075 repo.copy(src, dst)
1076 if (not similarity) and removes:
1077 repo.remove(sorted(removes), True)
1078 for f in patches:
1079 gp = patches[f]
1080 if gp and gp.mode:
1081 islink, isexec = gp.mode
1082 dst = repo.wjoin(gp.path)
1083 # patch won't create empty files
1084 if gp.op == 'ADD' and not os.path.exists(dst):
1085 flags = (isexec and 'x' or '') + (islink and 'l' or '')
1086 repo.wwrite(gp.path, '', flags)
1087 elif gp.op != 'DELETE':
1088 util.set_flags(dst, islink, isexec)
1089 cmdutil.addremove(repo, cfiles, similarity=similarity)
1090 files = patches.keys()
1091 files.extend([r for r in removes if r not in files])
1092 return sorted(files)
1093
1094 def externalpatch(patcher, args, patchname, ui, strip, cwd, files):
1095 """use <patcher> to apply <patchname> to the working directory.
1096 returns whether patch was applied with fuzz factor."""
1097
1098 fuzz = False
1099 if cwd:
1100 args.append('-d %s' % util.shellquote(cwd))
1101 fp = util.popen('%s %s -p%d < %s' % (patcher, ' '.join(args), strip,
1102 util.shellquote(patchname)))
1103
1104 for line in fp:
1105 line = line.rstrip()
1106 ui.note(line + '\n')
1107 if line.startswith('patching file '):
1108 pf = util.parse_patch_output(line)
1109 printed_file = False
1110 files.setdefault(pf, None)
1111 elif line.find('with fuzz') >= 0:
1112 fuzz = True
1113 if not printed_file:
1114 ui.warn(pf + '\n')
1115 printed_file = True
1116 ui.warn(line + '\n')
1117 elif line.find('saving rejects to file') >= 0:
1118 ui.warn(line + '\n')
1119 elif line.find('FAILED') >= 0:
1120 if not printed_file:
1121 ui.warn(pf + '\n')
1122 printed_file = True
1123 ui.warn(line + '\n')
1124 code = fp.close()
1125 if code:
1126 raise PatchError(_("patch command failed: %s") %
1127 util.explain_exit(code)[0])
1128 return fuzz
1129
1130 def internalpatch(patchobj, ui, strip, cwd, files={}, eolmode='strict'):
1131 """use builtin patch to apply <patchobj> to the working directory.
1132 returns whether patch was applied with fuzz factor."""
1133
1134 if eolmode is None:
1135 eolmode = ui.config('patch', 'eol', 'strict')
1136 try:
1137 eol = {'strict': None, 'crlf': '\r\n', 'lf': '\n'}[eolmode.lower()]
1138 except KeyError:
1139 raise util.Abort(_('Unsupported line endings type: %s') % eolmode)
1140
1141 try:
1142 fp = file(patchobj, 'rb')
1143 except TypeError:
1144 fp = patchobj
1145 if cwd:
1146 curdir = os.getcwd()
1147 os.chdir(cwd)
1148 try:
1149 ret = applydiff(ui, fp, files, strip=strip, eol=eol)
1150 finally:
1151 if cwd:
1152 os.chdir(curdir)
1153 if ret < 0:
1154 raise PatchError
1155 return ret > 0
1156
1157 def patch(patchname, ui, strip=1, cwd=None, files={}, eolmode='strict'):
1158 """Apply <patchname> to the working directory.
1159
1160 'eolmode' specifies how end of lines should be handled. It can be:
1161 - 'strict': inputs are read in binary mode, EOLs are preserved
1162 - 'crlf': EOLs are ignored when patching and reset to CRLF
1163 - 'lf': EOLs are ignored when patching and reset to LF
1164 - None: get it from user settings, default to 'strict'
1165 'eolmode' is ignored when using an external patcher program.
1166
1167 Returns whether patch was applied with fuzz factor.
1168 """
1169 patcher = ui.config('ui', 'patch')
1170 args = []
1171 try:
1172 if patcher:
1173 return externalpatch(patcher, args, patchname, ui, strip, cwd,
1174 files)
1175 else:
1176 try:
1177 return internalpatch(patchname, ui, strip, cwd, files, eolmode)
1178 except NoHunks:
1179 patcher = util.find_exe('gpatch') or util.find_exe('patch') or 'patch'
1180 ui.debug(_('no valid hunks found; trying with %r instead\n') %
1181 patcher)
1182 if util.needbinarypatch():
1183 args.append('--binary')
1184 return externalpatch(patcher, args, patchname, ui, strip, cwd,
1185 files)
1186 except PatchError, err:
1187 s = str(err)
1188 if s:
1189 raise util.Abort(s)
1190 else:
1191 raise util.Abort(_('patch failed to apply'))
1192
1193 def b85diff(to, tn):
1194 '''print base85-encoded binary diff'''
1195 def gitindex(text):
1196 if not text:
1197 return '0' * 40
1198 l = len(text)
1199 s = util.sha1('blob %d\0' % l)
1200 s.update(text)
1201 return s.hexdigest()
1202
1203 def fmtline(line):
1204 l = len(line)
1205 if l <= 26:
1206 l = chr(ord('A') + l - 1)
1207 else:
1208 l = chr(l - 26 + ord('a') - 1)
1209 return '%c%s\n' % (l, base85.b85encode(line, True))
1210
1211 def chunk(text, csize=52):
1212 l = len(text)
1213 i = 0
1214 while i < l:
1215 yield text[i:i+csize]
1216 i += csize
1217
1218 tohash = gitindex(to)
1219 tnhash = gitindex(tn)
1220 if tohash == tnhash:
1221 return ""
1222
1223 # TODO: deltas
1224 ret = ['index %s..%s\nGIT binary patch\nliteral %s\n' %
1225 (tohash, tnhash, len(tn))]
1226 for l in chunk(zlib.compress(tn)):
1227 ret.append(fmtline(l))
1228 ret.append('\n')
1229 return ''.join(ret)
1230
1231 def _addmodehdr(header, omode, nmode):
1232 if omode != nmode:
1233 header.append('old mode %s\n' % omode)
1234 header.append('new mode %s\n' % nmode)
1235
1236 def diff(repo, node1=None, node2=None, match=None, changes=None, opts=None):
1237 '''yields diff of changes to files between two nodes, or node and
1238 working directory.
1239
1240 if node1 is None, use first dirstate parent instead.
1241 if node2 is None, compare node1 with working directory.'''
1242
1243 if opts is None:
1244 opts = mdiff.defaultopts
1245
1246 if not node1:
1247 node1 = repo.dirstate.parents()[0]
1248
1249 def lrugetfilectx():
1250 cache = {}
1251 order = []
1252 def getfilectx(f, ctx):
1253 fctx = ctx.filectx(f, filelog=cache.get(f))
1254 if f not in cache:
1255 if len(cache) > 20:
1256 del cache[order.pop(0)]
1257 cache[f] = fctx._filelog
1258 else:
1259 order.remove(f)
1260 order.append(f)
1261 return fctx
1262 return getfilectx
1263 getfilectx = lrugetfilectx()
1264
1265 ctx1 = repo[node1]
1266 ctx2 = repo[node2]
1267
1268 if not changes:
1269 changes = repo.status(ctx1, ctx2, match=match)
1270 modified, added, removed = changes[:3]
1271
1272 if not modified and not added and not removed:
1273 return
1274
1275 date1 = util.datestr(ctx1.date())
1276 man1 = ctx1.manifest()
1277
1278 if repo.ui.quiet:
1279 r = None
1280 else:
1281 hexfunc = repo.ui.debugflag and hex or short
1282 r = [hexfunc(node) for node in [node1, node2] if node]
1283
1284 if opts.git:
1285 copy, diverge = copies.copies(repo, ctx1, ctx2, repo[nullid])
1286 copy = copy.copy()
1287 for k, v in copy.items():
1288 copy[v] = k
1289
1290 gone = set()
1291 gitmode = {'l': '120000', 'x': '100755', '': '100644'}
1292
1293 for f in sorted(modified + added + removed):
1294 to = None
1295 tn = None
1296 dodiff = True
1297 header = []
1298 if f in man1:
1299 to = getfilectx(f, ctx1).data()
1300 if f not in removed:
1301 tn = getfilectx(f, ctx2).data()
1302 a, b = f, f
1303 if opts.git:
1304 if f in added:
1305 mode = gitmode[ctx2.flags(f)]
1306 if f in copy:
1307 a = copy[f]
1308 omode = gitmode[man1.flags(a)]
1309 _addmodehdr(header, omode, mode)
1310 if a in removed and a not in gone:
1311 op = 'rename'
1312 gone.add(a)
1313 else:
1314 op = 'copy'
1315 header.append('%s from %s\n' % (op, a))
1316 header.append('%s to %s\n' % (op, f))
1317 to = getfilectx(a, ctx1).data()
1318 else:
1319 header.append('new file mode %s\n' % mode)
1320 if util.binary(tn):
1321 dodiff = 'binary'
1322 elif f in removed:
1323 # have we already reported a copy above?
1324 if f in copy and copy[f] in added and copy[copy[f]] == f:
1325 dodiff = False
1326 else:
1327 header.append('deleted file mode %s\n' %
1328 gitmode[man1.flags(f)])
1329 else:
1330 omode = gitmode[man1.flags(f)]
1331 nmode = gitmode[ctx2.flags(f)]
1332 _addmodehdr(header, omode, nmode)
1333 if util.binary(to) or util.binary(tn):
1334 dodiff = 'binary'
1335 r = None
1336 header.insert(0, mdiff.diffline(r, a, b, opts))
1337 if dodiff:
1338 if dodiff == 'binary':
1339 text = b85diff(to, tn)
1340 else:
1341 text = mdiff.unidiff(to, date1,
1342 # ctx2 date may be dynamic
1343 tn, util.datestr(ctx2.date()),
1344 a, b, r, opts=opts)
1345 if header and (text or len(header) > 1):
1346 yield ''.join(header)
1347 if text:
1348 yield text
1349
1350 def export(repo, revs, template='hg-%h.patch', fp=None, switch_parent=False,
1351 opts=None):
1352 '''export changesets as hg patches.'''
1353
1354 total = len(revs)
1355 revwidth = max([len(str(rev)) for rev in revs])
1356
1357 def single(rev, seqno, fp):
1358 ctx = repo[rev]
1359 node = ctx.node()
1360 parents = [p.node() for p in ctx.parents() if p]
1361 branch = ctx.branch()
1362 if switch_parent:
1363 parents.reverse()
1364 prev = (parents and parents[0]) or nullid
1365
1366 if not fp:
1367 fp = cmdutil.make_file(repo, template, node, total=total,
1368 seqno=seqno, revwidth=revwidth,
1369 mode='ab')
1370 if fp != sys.stdout and hasattr(fp, 'name'):
1371 repo.ui.note("%s\n" % fp.name)
1372
1373 fp.write("# HG changeset patch\n")
1374 fp.write("# User %s\n" % ctx.user())
1375 fp.write("# Date %d %d\n" % ctx.date())
1376 if branch and (branch != 'default'):
1377 fp.write("# Branch %s\n" % branch)
1378 fp.write("# Node ID %s\n" % hex(node))
1379 fp.write("# Parent %s\n" % hex(prev))
1380 if len(parents) > 1:
1381 fp.write("# Parent %s\n" % hex(parents[1]))
1382 fp.write(ctx.description().rstrip())
1383 fp.write("\n\n")
1384
1385 for chunk in diff(repo, prev, node, opts=opts):
1386 fp.write(chunk)
1387
1388 for seqno, rev in enumerate(revs):
1389 single(rev, seqno+1, fp)
1390
1391 def diffstatdata(lines):
1392 filename, adds, removes = None, 0, 0
1393 for line in lines:
1394 if line.startswith('diff'):
1395 if filename:
1396 yield (filename, adds, removes)
1397 # set numbers to 0 anyway when starting new file
1398 adds, removes = 0, 0
1399 if line.startswith('diff --git'):
1400 filename = gitre.search(line).group(1)
1401 else:
1402 # format: "diff -r ... -r ... filename"
1403 filename = line.split(None, 5)[-1]
1404 elif line.startswith('+') and not line.startswith('+++'):
1405 adds += 1
1406 elif line.startswith('-') and not line.startswith('---'):
1407 removes += 1
1408 if filename:
1409 yield (filename, adds, removes)
1410
1411 def diffstat(lines, width=80):
1412 output = []
1413 stats = list(diffstatdata(lines))
1414
1415 maxtotal, maxname = 0, 0
1416 totaladds, totalremoves = 0, 0
1417 for filename, adds, removes in stats:
1418 totaladds += adds
1419 totalremoves += removes
1420 maxname = max(maxname, len(filename))
1421 maxtotal = max(maxtotal, adds+removes)
1422
1423 countwidth = len(str(maxtotal))
1424 graphwidth = width - countwidth - maxname
1425 if graphwidth < 10:
1426 graphwidth = 10
1427
1428 factor = max(int(math.ceil(float(maxtotal) / graphwidth)), 1)
1429
1430 for filename, adds, removes in stats:
1431 # If diffstat runs out of room it doesn't print anything, which
1432 # isn't very useful, so always print at least one + or - if there
1433 # were at least some changes
1434 pluses = '+' * max(adds/factor, int(bool(adds)))
1435 minuses = '-' * max(removes/factor, int(bool(removes)))
1436 output.append(' %-*s | %*.d %s%s\n' % (maxname, filename, countwidth,
1437 adds+removes, pluses, minuses))
1438
1439 if stats:
1440 output.append(' %d files changed, %d insertions(+), %d deletions(-)\n'
1441 % (len(stats), totaladds, totalremoves))
1442
1443 return ''.join(output)