text: import difflib
  import re
  
  from bs4 import BeautifulSoup
  from bs4.element import NavigableString, CData, Tag
  from django.utils.encoding import force_str
  from django.utils.html import escape, format_html, format_html_join
  from django.utils.safestring import mark_safe
  from django.utils.text import capfirst
  from django.utils.translation import ugettext_lazy as _
  
  from wagtail.core import blocks
  
  
  class Render:
      skip = False
  
      def render(self, item):
          if self.skip:
              self.skip = False
              return
          if isinstance(item, NavigableString):
              return item
          if isinstance(item, CData):
              return item
          if isinstance(item, Tag) and item.name == 'a':
              text = ''.join(item.contents)
              url = item.attrs['href']
              self.skip = True
              return f'[{text}={url}]'
  
  
  def text_from_html(val):
      # Return the unescaped text content of an HTML string
      bs = BeautifulSoup(force_str(val), 'html5lib')
      renderer = Render()
      parts = [renderer.render(x) for x in bs.descendants]
      parts = [x for x in parts if x is not None]
      joined = ' '.join(parts)
      joined = re.sub(r'\s+', ' ', joined)
      return joined
  
  
  class FieldComparison:
      is_field = True
      is_child_relation = False
  
      def __init__(self, field, obj_a, obj_b):
          self.field = field
          self.val_a = field.value_from_object(obj_a)
          self.val_b = field.value_from_object(obj_b)
  
      def field_label(self):
          """
          Returns a label for this field to be displayed to the user
          """
          verbose_name = getattr(self.field, 'verbose_name', None)
  
          if verbose_name is None:
              # Relations don't have a verbose_name
              verbose_name = self.field.name.replace('_', ' ')
  
          return capfirst(verbose_name)
  
      def htmldiff(self):
          if self.val_a != self.val_b:
              return TextDiff([('deletion', self.val_a), ('addition', self.val_b)]).to_html()
          else:
              return escape(self.val_a)
  
      def has_changed(self):
          """
          Returns True if the field has changed
          """
          return self.val_a != self.val_b
  
  
  class TextFieldComparison(FieldComparison):
      def htmldiff(self):
          return diff_text(self.val_a, self.val_b).to_html()
  
  
  class RichTextFieldComparison(TextFieldComparison):
      def htmldiff(self):
          return diff_text(
              text_from_html(self.val_a),
              text_from_html(self.val_b)
          ).to_html()
  
  
  def get_comparison_class_for_block(block):
      if hasattr(block, 'get_comparison_class'):
          return block.get_comparison_class()
      elif isinstance(block, (blocks.CharBlock, blocks.TextBlock)):
          return CharBlockComparison
      elif isinstance(block, blocks.RawHTMLBlock):
          # Compare raw HTML blocks as if they were plain text, so that tags are shown explicitly
          return CharBlockComparison
      elif isinstance(block, blocks.RichTextBlock):
          return RichTextBlockComparison
      elif isinstance(block, blocks.StructBlock):
          return StructBlockComparison
      else:
          # As all stream field blocks have a HTML representation, fall back to diffing that.
          return RichTextBlockComparison
  
  
  class BlockComparison:
      def __init__(self, block, exists_a, exists_b, val_a, val_b):
          self.block = block
          self.exists_a = exists_a
          self.exists_b = exists_b
          self.val_a = val_a
          self.val_b = val_b
  
      def is_new(self):
          return self.exists_b and not self.exists_a
  
      def is_deleted(self):
          return self.exists_a and not self.exists_b
  
      def has_changed(self):
          return self.val_a != self.val_b
  
      def htmlvalue(self, val):
          """
          Return an HTML representation of this block that is safe to be included
          in comparison views
          """
          return escape(text_from_html(self.block.render_basic(val)))
  
      def htmldiff(self):
          html_val_a = self.block.render_basic(self.val_a)
          html_val_b = self.block.render_basic(self.val_b)
          return diff_text(
              text_from_html(html_val_a),
              text_from_html(html_val_b)
          ).to_html()
  
  
  class CharBlockComparison(BlockComparison):
      def htmldiff(self):
          return diff_text(
              force_str(self.val_a),
              force_str(self.val_b)
          ).to_html()
  
      def htmlvalue(self, val):
          return escape(val)
  
  
  class RichTextBlockComparison(BlockComparison):
      pass
  
  
  class StructBlockComparison(BlockComparison):
      def htmlvalue(self, val):
          htmlvalues = []
          for name, block in self.block.child_blocks.items():
              label = self.block.child_blocks[name].label
              comparison_class = get_comparison_class_for_block(block)
  
              htmlvalues.append((label, comparison_class(block, True, True, val[name], val[name]).htmlvalue(val[name])))
  
          return format_html('<dl>\n{}\n</dl>', format_html_join(
              '\n', '    <dt>{}</dt>\n    <dd>{}</dd>', htmlvalues))
  
      def htmldiff(self):
          htmldiffs = []
          for name, block in self.block.child_blocks.items():
              label = self.block.child_blocks[name].label
              comparison_class = get_comparison_class_for_block(block)
  
              htmldiffs.append((label, comparison_class(block, self.exists_a, self.exists_b, self.val_a[name], self.val_b[name]).htmldiff()))
  
          return format_html('<dl>\n{}\n</dl>', format_html_join(
              '\n', '    <dt>{}</dt>\n    <dd>{}</dd>', htmldiffs))
  
  
  class StreamBlockComparison(BlockComparison):
      def get_block_comparisons(self):
          a_blocks = list(self.val_a) or []
          b_blocks = list(self.val_b) or []
  
          a_blocks_by_id = {block.id: block for block in a_blocks}
          b_blocks_by_id = {block.id: block for block in b_blocks}
  
          deleted_ids = a_blocks_by_id.keys() - b_blocks_by_id.keys()
  
          comparisons = []
          for block in b_blocks:
              comparison_class = get_comparison_class_for_block(block.block)
  
              if block.id in a_blocks_by_id:
                  # Changed/existing block
                  comparisons.append(comparison_class(block.block, True, True, a_blocks_by_id[block.id].value, block.value))
              else:
                  # New block
                  comparisons.append(comparison_class(block.block, False, True, None, block.value))
  
          # Insert deleted blocks at the index where they used to be
          deleted_block_indices = [(block, i) for i, block in enumerate(a_blocks) if block.id in deleted_ids]
  
          for block, index in deleted_block_indices:
              comparison_class = get_comparison_class_for_block(block.block)
              comparison_to_insert = comparison_class(block.block, True, False, block.value, None)
  
              # Insert the block back in where it was before it was deleted.
              # Note: we need to account for new blocks when finding the position.
              current_index = 0
              block_inserted = False
              for i, comparison in enumerate(comparisons):
                  if comparison.is_new():
                      continue
  
                  if current_index == index:
                      comparisons.insert(i, comparison_to_insert)
                      block_inserted = True
                      break
  
                  current_index += 1
  
              # Deleted block was from the end
              if not block_inserted:
                  comparisons.append(comparison_to_insert)
  
          return comparisons
  
      def htmldiff(self):
          comparisons_html = []
  
          for comparison in self.get_block_comparisons():
              classes = ['comparison__child-object']
              if comparison.is_new():
                  classes.append('addition')
                  block_rendered = comparison.htmlvalue(comparison.val_b)
              elif comparison.is_deleted():
                  classes.append('deletion')
                  block_rendered = comparison.htmlvalue(comparison.val_a)
              elif comparison.has_changed():
                  block_rendered = comparison.htmldiff()
              else:
                  block_rendered = comparison.htmlvalue(comparison.val_a)
  
              classes = ' '.join(classes)
              comparisons_html.append('<div class="{0}">{1}</div>'.format(classes, block_rendered))
  
          return mark_safe('\n'.join(comparisons_html))
  
  
  class StreamFieldComparison(FieldComparison):
      def has_block_ids(self, val):
          if not val:
              return True
  
          return bool(val[0].id)
  
      def htmldiff(self):
          # Our method for diffing streamfields relies on the blocks in both revisions having UUIDs.
          # But as UUIDs were added in Wagtail 1.11 we can't compare revisions that were created before
          # that Wagtail version.
          if self.has_block_ids(self.val_a) and self.has_block_ids(self.val_b):
              return StreamBlockComparison(self.field.stream_block, True, True, self.val_a, self.val_b).htmldiff()
          else:
              # Fall back to diffing the HTML representation
              return diff_text(
                  text_from_html(self.val_a),
                  text_from_html(self.val_b)
              ).to_html()
  
  
  class ChoiceFieldComparison(FieldComparison):
      def htmldiff(self):
          val_a = force_str(dict(self.field.flatchoices).get(self.val_a, self.val_a), strings_only=True)
          val_b = force_str(dict(self.field.flatchoices).get(self.val_b, self.val_b), strings_only=True)
  
          if self.val_a != self.val_b:
              diffs = []
  
              if val_a:
                  diffs += [('deletion', val_a)]
              if val_b:
                  diffs += [('addition', val_b)]
  
              return TextDiff(diffs).to_html()
          else:
              return escape(val_a)
  
  
  class M2MFieldComparison(FieldComparison):
      def get_items(self):
          return list(self.val_a), list(self.val_b)
  
      def get_item_display(self, item):
          return str(item)
  
      def htmldiff(self):
          # Get tags
          items_a, items_b = self.get_items()
  
          # Calculate changes
          sm = difflib.SequenceMatcher(0, items_a, items_b)
          changes = []
          for op, i1, i2, j1, j2 in sm.get_opcodes():
              if op == 'replace':
                  for item in items_a[i1:i2]:
                      changes.append(('deletion', self.get_item_display(item)))
                  for item in items_b[j1:j2]:
                      changes.append(('addition', self.get_item_display(item)))
              elif op == 'delete':
                  for item in items_a[i1:i2]:
                      changes.append(('deletion', self.get_item_display(item)))
              elif op == 'insert':
                  for item in items_b[j1:j2]:
                      changes.append(('addition', self.get_item_display(item)))
              elif op == 'equal':
                  for item in items_a[i1:i2]:
                      changes.append(('equal', self.get_item_display(item)))
  
          # Convert changelist to HTML
          return TextDiff(changes, separator=", ").to_html()
  
      def has_changed(self):
          items_a, items_b = self.get_items()
          return items_a != items_b
  
  
  class TagsFieldComparison(M2MFieldComparison):
      def get_item_display(self, tag):
          return tag.slug
  
  
  class ForeignObjectComparison(FieldComparison):
      def get_objects(self):
          model = self.field.related_model
          obj_a = model.objects.filter(pk=self.val_a).first()
          obj_b = model.objects.filter(pk=self.val_b).first()
          return obj_a, obj_b
  
      def htmldiff(self):
          obj_a, obj_b = self.get_objects()
  
          if obj_a != obj_b:
              if obj_a and obj_b:
                  # Changed
                  return TextDiff([('deletion', force_str(obj_a)), ('addition', force_str(obj_b))]).to_html()
              elif obj_b:
                  # Added
                  return TextDiff([('addition', force_str(obj_b))]).to_html()
              elif obj_a:
                  # Removed
                  return TextDiff([('deletion', force_str(obj_a))]).to_html()
          else:
              if obj_a:
                  return escape(force_str(obj_a))
              else:
                  return _("None")
  
  
  class ChildRelationComparison:
      is_field = False
      is_child_relation = True
  
      def __init__(self, field, field_comparisons, obj_a, obj_b):
          self.field = field
          self.field_comparisons = field_comparisons
          self.val_a = getattr(obj_a, field.related_name)
          self.val_b = getattr(obj_b, field.related_name)
  
      def field_label(self):
          """
          Returns a label for this field to be displayed to the user
          """
          verbose_name = getattr(self.field, 'verbose_name', None)
  
          if verbose_name is None:
              # Relations don't have a verbose_name
              verbose_name = self.field.name.replace('_', ' ')
  
          return capfirst(verbose_name)
  
      def get_mapping(self, objs_a, objs_b):
          """
          This bit of code attempts to match the objects in the A revision with
          their counterpart in the B revision.
  
          A match is firstly attempted by PK (where a matching ID indicates they're the same).
          We compare remaining the objects by their field data; the objects with the fewest
          fields changed are matched until there are no more possible matches left.
  
          This returns 4 values:
           - map_forwards => a mapping of object indexes from the B version to the A version
           - map_backwards => a mapping of object indexes from the A version to the B version
           - added => a list of indices for objects that didn't exist in the B version
           - deleted => a list of indices for objects that didn't exist in the A version
  
          Note the indices are 0-based array indices indicating the location of the object in either
          the objs_a or objs_b arrays.
  
          For example:
  
          objs_a => A, B, C, D
          objs_b => B, C, D, E
  
          Will return the following:
  
          map_forwards = {
              1: 0,  # B (objs_a: objs_b)
              2: 1,  # C (objs_a: objs_b)
              3: 2,  # D (objs_a: objs_b)
          }
          map_backwards = {
              0: 1,  # B (objs_b: objs_a)
              1: 2,  # C (objs_b: objs_a)
              2: 3,  # D (objs_b: objs_a)
          }
          added = [4]  # D in objs_b
          deleted = [0]  # A in objs_a
          """
          map_forwards = {}
          map_backwards = {}
          added = []
          deleted = []
  
          # Match child objects on PK (ID)
          for a_idx, a_child in enumerate(objs_a):
              for b_idx, b_child in enumerate(objs_b):
                  if b_idx in map_backwards:
                      continue
  
                  if a_child.pk is not None and b_child.pk is not None and a_child.pk == b_child.pk:
                      map_forwards[a_idx] = b_idx
                      map_backwards[b_idx] = a_idx
  
          # Now try to match them by data
          matches = []
          for a_idx, a_child in enumerate(objs_a):
              if a_idx not in map_forwards:
                  for b_idx, b_child in enumerate(objs_b):
                      if b_idx not in map_backwards:
                          # If they both have a PK (ID) that is different, they can't be the same child object
                          if a_child.pk and b_child.pk and a_child.pk != b_child.pk:
                              continue
  
                          comparison = self.get_child_comparison(objs_a[a_idx], objs_b[b_idx])
                          num_differences = comparison.get_num_differences()
  
                          matches.append((a_idx, b_idx, num_differences))
  
          # Objects with the least differences will be matched first. So only the best possible matches are made
          matches.sort(key=lambda match: match[2])
          for a_idx, b_idx, num_differences in matches:
              # Make sure both objects were not matched previously
              if a_idx in map_forwards or b_idx in map_backwards:
                  continue
  
              # Match!
              map_forwards[a_idx] = b_idx
              map_backwards[b_idx] = a_idx
  
          # Mark unmapped objects as added/deleted
          for a_idx, a_child in enumerate(objs_a):
              if a_idx not in map_forwards:
                  deleted.append(a_idx)
  
          for b_idx, b_child in enumerate(objs_b):
              if b_idx not in map_backwards:
                  added.append(b_idx)
  
          return map_forwards, map_backwards, added, deleted
  
      def get_child_comparison(self, obj_a, obj_b):
          return ChildObjectComparison(self.field.related_model, self.field_comparisons, obj_a, obj_b)
  
      def get_child_comparisons(self):
          """
          Returns a list of ChildObjectComparison objects. Representing all child
          objects that existed in either version.
  
          They are returned in the order they appear in the B version with deletions
          appended at the end.
  
          All child objects are returned, regardless of whether they were actually changed.
          """
          objs_a = list(self.val_a.all())
          objs_b = list(self.val_b.all())
  
          map_forwards, map_backwards, added, deleted = self.get_mapping(objs_a, objs_b)
          objs_a = dict(enumerate(objs_a))
          objs_b = dict(enumerate(objs_b))
  
          comparisons = []
  
          for b_idx, b_child in objs_b.items():
              if b_idx in added:
                  comparisons.append(self.get_child_comparison(None, b_child))
              else:
                  comparisons.append(self.get_child_comparison(objs_a[map_backwards[b_idx]], b_child))
  
          for a_idx, a_child in objs_a.items():
              if a_idx in deleted:
                  comparisons.append(self.get_child_comparison(a_child, None))
  
          return comparisons
  
      def has_changed(self):
          """
          Returns true if any changes were made to any of the child objects. This includes
          adding, deleting and reordering.
          """
          objs_a = list(self.val_a.all())
          objs_b = list(self.val_b.all())
  
          map_forwards, map_backwards, added, deleted = self.get_mapping(objs_a, objs_b)
  
          if added or deleted:
              return True
  
          for a_idx, b_idx in map_forwards.items():
              comparison = self.get_child_comparison(objs_a[a_idx], objs_b[b_idx])
  
              if comparison.has_changed():
                  return True
  
          return False
  
  
  class ChildObjectComparison:
      def __init__(self, model, field_comparisons, obj_a, obj_b):
          self.model = model
          self.field_comparisons = field_comparisons
          self.obj_a = obj_a
          self.obj_b = obj_b
  
      def is_addition(self):
          """
          Returns True if this child object was created since obj_a
          """
          return self.obj_b and not self.obj_a
  
      def is_deletion(self):
          """
          Returns True if this child object was deleted in obj_b
          """
          return self.obj_a and not self.obj_b
  
      def get_position_change(self):
          """
          Returns the change in position as an integer. Positive if the object
          was moved down, negative if it moved up.
  
          For example: '3' indicates the object moved down three spaces. '-1'
          indicates the object moved up one space.
          """
          if not self.is_addition() and not self.is_deletion():
              sort_a = getattr(self.obj_a, 'sort_order', 0) or 0
              sort_b = getattr(self.obj_b, 'sort_order', 0) or 0
              return sort_b - sort_a
  
      def get_field_comparisons(self):
          """
          Returns a list of comparisons for all the fields in this object.
          Fields that haven't changed are included as well.
          """
          comparisons = []
  
          if self.is_addition() or self.is_deletion():
              # Display the fields without diff as one of the versions are missing
              obj = self.obj_a or self.obj_b
  
              for field_comparison in self.field_comparisons:
                  comparisons.append(field_comparison(obj, obj))
          else:
              for field_comparison in self.field_comparisons:
                  comparisons.append(field_comparison(self.obj_a, self.obj_b))
  
          return comparisons
  
      def has_changed(self):
          for comparison in self.get_field_comparisons():
              if comparison.has_changed():
                  return True
  
          return False
  
      def get_num_differences(self):
          """
          Returns the number of fields that differ between the two
          objects.
          """
          num_differences = 0
  
          for comparison in self.get_field_comparisons():
              if comparison.has_changed():
                  num_differences += 1
  
          return num_differences
  
  
  class TextDiff:
      def __init__(self, changes, separator=""):
          self.changes = changes
          self.separator = separator
  
      def to_html(self, tag='span', addition_class='addition', deletion_class='deletion'):
          html = []
  
          for change_type, value in self.changes:
              if change_type == 'equal':
                  html.append(escape(value))
              elif change_type == 'addition':
                  html.append('<{tag} class="{classname}">{value}</{tag}>'.format(
                      tag=tag,
                      classname=addition_class,
                      value=escape(value)
                  ))
              elif change_type == 'deletion':
                  html.append('<{tag} class="{classname}">{value}</{tag}>'.format(
                      tag=tag,
                      classname=deletion_class,
                      value=escape(value)
                  ))
  
          return mark_safe(self.separator.join(html))
  
  
  def diff_text(a, b):
      """
      Performs a diffing algorithm on two pieces of text. Returns
      a string of HTML containing the content of both texts with
      <span> tags inserted indicating where the differences are.
      """
      def tokenise(text):
          """
          Tokenises a string by spliting it into individual characters
          and grouping the alphanumeric ones together.
  
          This means that punctuation, whitespace, CJK characters, etc
          become separate tokens and words/numbers are merged together
          to form bigger tokens.
  
          This makes the output of the diff easier to read as words are
          not broken up.
          """
          tokens = []
          current_token = ""
  
          for c in text or "":
              if c.isalnum():
                  current_token += c
              else:
                  if current_token:
                      tokens.append(current_token)
                      current_token = ""
  
                  tokens.append(c)
  
          if current_token:
              tokens.append(current_token)
  
          return tokens
  
      a_tok = tokenise(a)
      b_tok = tokenise(b)
      sm = difflib.SequenceMatcher(lambda t: len(t) <= 4, a_tok, b_tok)
  
      changes = []
  
      for op, i1, i2, j1, j2 in sm.get_opcodes():
          if op == 'replace':
              for token in a_tok[i1:i2]:
                  changes.append(('deletion', token))
              for token in b_tok[j1:j2]:
                  changes.append(('addition', token))
          elif op == 'delete':
              for token in a_tok[i1:i2]:
                  changes.append(('deletion', token))
          elif op == 'insert':
              for token in b_tok[j1:j2]:
                  changes.append(('addition', token))
          elif op == 'equal':
              for token in a_tok[i1:i2]:
                  changes.append(('equal', token))
  
      # Merge ajacent changes which have the same type. This just cleans up the HTML a bit
      merged_changes = []
      current_value = []
      current_change_type = None
      for change_type, value in changes:
          if change_type != current_change_type:
              if current_change_type is not None:
                  merged_changes.append((current_change_type, ''.join(current_value)))
                  current_value = []
  
              current_change_type = change_type
  
          current_value.append(value)
  
      if current_value:
          merged_changes.append((current_change_type, ''.join(current_value)))
  
      return TextDiff(merged_changes)
  