lib/diff_internal.h

   1 /* Generic infrastructure to implement various diff algorithms. */
   2 /*
   3  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 #ifndef MAX
  19 #define MAX(A,B) ((A)>(B)?(A):(B))
  20 #endif
  21 #ifndef MIN
  22 #define MIN(A,B) ((A)<(B)?(A):(B))
  23 #endif
  24
  25 static inline bool
  26 diff_range_empty(const struct diff_range *r)
  27 {
  28         return r->start == r->end;
  29 }
  30
  31 static inline bool
  32 diff_ranges_touch(const struct diff_range *a, const struct diff_range *b)
  33 {
  34         return (a->end >= b->start) && (a->start <= b->end);
  35 }
  36
  37 static inline void
  38 diff_ranges_merge(struct diff_range *a, const struct diff_range *b)
  39 {
  40         *a = (struct diff_range){
  41                 .start = MIN(a->start, b->start),
  42                 .end = MAX(a->end, b->end),
  43         };
  44 }
  45
  46 static inline int
  47 diff_range_len(const struct diff_range *r)
  48 {
  49         if (!r)
  50                 return 0;
  51         return r->end - r->start;
  52 }
  53
  54 /* Indicate whether two given diff atoms match. */
  55 int
  56 diff_atom_same(bool *same,
  57                const struct diff_atom *left,
  58                const struct diff_atom *right);
  59
  60 /* A diff chunk represents a set of atoms on the left and/or a set of atoms on
  61  * the right.
  62  *
  63  * If solved == false:
  64  * The diff algorithm has divided the source file, and this is a chunk that the
  65  * inner_algo should run on next.
  66  * The lines on the left should be diffed against the lines on the right.
  67  * (If there are no left lines or no right lines, it implies solved == true,
  68  * because there is nothing to diff.)
  69  *
  70  * If solved == true:
  71  * If there are only left atoms, it is a chunk removing atoms from the left ("a
  72  * minus chunk").
  73  * If there are only right atoms, it is a chunk adding atoms from the right ("a
  74  * plus chunk").
  75  * If there are both left and right lines, it is a chunk of equal content on
  76  * both sides, and left_count == right_count:
  77  *
  78  * - foo  }
  79  * - bar  }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
  80  * - baz  }               right_start = NULL, right_count = 0 }
  81  *   moo    }
  82  *   goo    }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
  83  *   zoo    }              right_start = &right.atoms.head[0], right_count = 3 }
  84  *  +loo      }
  85  *  +roo      }-- diff_chunk{ left_start = NULL, left_count = 0,
  86  *  +too      }            right_start = &right.atoms.head[3], right_count = 3 }
  87  *
  88  */
  89 struct diff_chunk {
  90         bool solved;
  91         struct diff_atom *left_start;
  92         unsigned int left_count;
  93         struct diff_atom *right_start;
  94         unsigned int right_count;
  95 };
  96
  97 #define DIFF_RESULT_ALLOC_BLOCKSIZE 128
  98
  99 struct diff_chunk_context;
 100
 101 bool
 102 diff_chunk_context_empty(const struct diff_chunk_context *cc);
 103
 104 bool
 105 diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
 106                           const struct diff_chunk_context *other);
 107
 108 void
 109 diff_chunk_contexts_merge(struct diff_chunk_context *cc,
 110                           const struct diff_chunk_context *other);
 111
 112 struct diff_state {
 113         /* The final result passed to the original diff caller. */
 114         struct diff_result *result;
 115
 116         /* The root diff_data is in result->left,right, these are (possibly)
 117          * subsections of the root data. */
 118         struct diff_data left;
 119         struct diff_data right;
 120
 121         unsigned int recursion_depth_left;
 122
 123         /* Remaining chunks from one diff algorithm pass, if any solved == false
 124          * chunks came up. */
 125         diff_chunk_arraylist_t temp_result;
 126
 127         /* State buffer used by Myers algorithm. */
 128         int *kd_buf;
 129         size_t kd_buf_size; /* in units of sizeof(int), not bytes */
 130 };
 131
 132 struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
 133                                         struct diff_atom *left_start,
 134                                         unsigned int left_count,
 135                                         struct diff_atom *right_start,
 136                                         unsigned int right_count);
 137
 138 struct diff_output_info;
 139
 140 int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
 141                        const char *prefix, struct diff_atom *start_atom,
 142                        unsigned int count);
 143
 144 int diff_output_trailing_newline_msg(struct diff_output_info *outinfo,
 145                                      FILE *dest,
 146                                      const struct diff_chunk *c);
 147 #define DIFF_FUNCTION_CONTEXT_SIZE      55
 148 int diff_output_match_function_prototype(char *prototype, size_t prototype_size,
 149                                          int *last_prototype_idx,
 150                                          const struct diff_result *result,
 151                                          const struct diff_chunk_context *cc,
 152                                          unsigned int ncontext);
 153
 154 struct diff_output_info *diff_output_info_alloc(void);
 155
 156 void
 157 diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
 158                           struct diff_atom *from_atom, unsigned int atoms_count);