awk/ref_match.awk

   1 #!/usr/bin/awk -f
   2
   3 # ref_match - TopGit awk utility script used by tg--awksome
   4 # Copyright (C) 2017 Kyle J. McKay <mackyle@gmail.com>
   5 # All rights reserved.
   6 # License GPLv2
   7
   8 # ref_match
   9 #
  10 #  pckdrefs  input refs are in packed-refs format
  11 #  patterns  whitespace-separated for-each-ref style patterns to match
  12 #  matchfmt  a for-each-ref format string (limited, see below)
  13 #  sortkey   optional "[-]<key>" or "[-]<key>,[-]<key>" (see below)
  14 #  dupesok   keep dupes in output (only works if patterns is empty or "refs")
  15 #  maxout    stop after no more matches than this
  16 #
  17 # NOTE: fnmatch (FNM_PATHNAME) style matches are not currently supported.
  18 #       All "patterns" must match exactly as a prefix at a "/" boundary
  19 #       (a "prefix" that is actually the entire ref matches too).
  20 #
  21 # input is a list of "<ref> <hash>" per line (or packed-refs style if
  22 # pckdrefs is true) if there are multiple entries for the same ref name
  23 # only one wins (which exactly is indeterminate since the sort is unstable).
  24 # However, if dupesok is true and there are no patterns (or the only pattern
  25 # is "refs" or "refs/") then refname duplicates will be kept in the output.
  26 #
  27 # hash values are always converted to lowercase
  28 #
  29 # output is each matching ref shown using the output matchfmt format whcih
  30 # is a limited form of the for-each-ref format in that the default is similar
  31 # to for-each-ref and only fields "%(refname)" and "%(objectname)" are
  32 # supported along with "%%" and "%xx" EXCEPT "%00" (it will try don't expect
  33 # it to work though) any other % sequence will pass through unchanged
  34 #
  35 # here is the actual format string (as a --format argument) used by default:
  36 #
  37 #   --format="%(objectname) object%09%(refname)"
  38 #
  39 # while this is similar the for-each-ref default it uses "object" for the object
  40 # type since one is not available and, in fact, %(objecttype) will indeed also
  41 # be replaced with "object"
  42 #
  43 # output will be sorted by "refname" by default (it's always sorted somehow)
  44 # and for the two-key form, the LAST key is the primary key; if the leading
  45 # "-" is present it's a descending sort instead of ascending; only "objectname"
  46 # and "refname" keys are supported (obviously)
  47 #
  48 # This one was supposed to be just a simple quick little thing *sigh*
  49 #
  50
  51 function arrayswp(anarray, i1, i2, _swapper) {
  52         _swapper = anarray[i1]
  53         anarray[i1] = anarray[i2]
  54         anarray[i2] = _swapper
  55         if (!multisort) return # ** cough **
  56         _swapper = hashes[i1]
  57         hashes[i1] = hashes[i2]
  58         hashes[i2] = _swapper
  59 }
  60
  61 function kasort_order3(anarray, i1, i2, i3, _c12, _c13, _c23) {
  62         _c12 = cmpkeys(anarray, i1, i2)
  63         _c23 = cmpkeys(anarray, i2, i3)
  64         if (_c12 <= 0) {
  65                 if (_c23 <= 0) return ((!_c12 && _c23) || (!_c23 && _c12)) ? -1 : 0
  66                 if (_c12 == 0) {
  67                         arrayswp(anarray, i1, i3)
  68                         return -1
  69                 }
  70         } else if (_c23 >= 0) {
  71                 arrayswp(anarray, i1, i3)
  72                 return _c23 ? 0 : -1
  73         }
  74         _c13 = cmpkeys(anarray, i1, i3)
  75         if (_c13 > 0) arrayswp(anarray, i1, i3)
  76         if (_c12 <= 0) arrayswp(anarray, i2, i3)
  77         else arrayswp(anarray, i1, i2)
  78         return 0
  79 }
  80
  81 # Could "ka" mean, oh I don't know, perhaps one of these?  ;)
  82 #   Kyle's Awesome alternative to the low iQ sort
  83 #   Kick Ass sort
  84 #   Kyle's Array sort
  85 #
  86 function kasort_partition(anarray, si, ei, _mi, _le, _ge, _o3, _n) {
  87         if (ei <= si) return
  88         if (si + 1 == ei) {
  89                 if (cmpkeys(anarray, si, ei) > 0)
  90                         arrayswp(anarray, si, ei)
  91                 return
  92         }
  93         _mi = int((si + ei) / 2)
  94         _n = ei - si
  95         if (_n >= 44) {
  96                 _n = int(_n / 8)
  97                 kasort_order3(anarray, si + _n, _mi, ei - _n)
  98         }
  99         _o3 = kasort_order3(anarray, si, _mi, ei)
 100         if (_n == 2) return
 101         _le = si
 102         _ge = ei
 103         while (1) {
 104                 if (_le < _mi)
 105                         while (++_le < _ge && _le != _mi && cmpkeys(anarray, _le, _mi) <= _o3) ;
 106                 if (_le < _ge)
 107                         while (_mi < _ge && _le < --_ge && cmpkeys(anarray, _mi, _ge) <= _o3) ;
 108                 if (_le < _ge && _ge <= _mi)
 109                         while (_le < --_ge && cmpkeys(anarray, _mi, _ge) < 0) ;
 110                 if (_mi <= _le && _le < _ge)
 111                         while (++_le < _ge && cmpkeys(anarray, _le, _mi) < 0) ;
 112                 if (_le < _ge) {
 113                         arrayswp(anarray, _le, _ge)
 114                         continue
 115                 }
 116                 if (_le < _mi) {
 117                         arrayswp(anarray, _le, _mi)
 118                         _mi = _le
 119                 } else if (_mi < _ge) {
 120                         arrayswp(anarray, _mi, _ge)
 121                         _mi = _ge
 122                 }
 123                 kasort_partition(anarray, si, _mi - 1)
 124                 kasort_partition(anarray, _mi + 1, ei)
 125                 return
 126         }
 127 }
 128
 129 function getpatarr(patstr,
 130         _p, _pi, _pc, _sa1, _c2, _sa2, _lpat, _llen, _i) {
 131
 132         split(patstr, _sa1, " ")
 133         _c2 = 0
 134         for (_pi in _sa1) {
 135                 _p = _sa1[_pi]
 136                 if (_p !~ /^refs\/[^\/]/) continue
 137                 sub(/\/+$/, "", _p)
 138                 _sa2[++_c2] = _p
 139         }
 140         _pc = 0
 141         if (_c2 > 1) {
 142                 kasort_partition(_sa2, 1, _c2)
 143                 _lpat = _sa2[1] "/"
 144                 _llen = length(_lpat)
 145                 patarr[++_pc] = _lpat
 146                 for (_i = 2; _i <= _c2; ++_i) {
 147                         _p = _sa2[_i] "/"
 148                         if (length(_p) >= _llen && _lpat == substr(_p, 1, _llen))
 149                                 continue
 150                         patarr[++_pc] = _p
 151                         _lpat = _p
 152                         _llen = length(_lpat)
 153                 }
 154         } else if (!_c2) {
 155                 patarr[++_pc] = "refs/"
 156         } else {
 157                 patarr[++_pc] = _sa2[1] "/"
 158         }
 159         patarr[_pc + 1] = "zend"
 160         return _pc
 161 }
 162
 163 BEGIN {
 164         multisort = 0
 165         dosortobj = 0
 166         cnt = 0
 167         sortobj = 0
 168         sortref = 0
 169         patcnt = getpatarr(patterns)
 170         for (i = split(tolower(sortkey), keys, /[, \t\r\n]+/); i >= 1; --i) {
 171                 if (keys[i] == "refname") {
 172                         sortref = 1
 173                         break
 174                 } else if (keys[i] == "-refname") {
 175                         sortref = -1
 176                         break
 177                 }
 178                 if (sortobj == 0 && keys[i] == "objectname") sortobj = 1
 179                 if (sortobj == 0 && keys[i] == "-objectname") sortobj = -1
 180         }
 181         if (!sortref) sortref = 1
 182         if (matchfmt == "") matchfmt = "%(objectname) %(objecttype)%09%(refname)"
 183         fc = split(matchfmt, fmts, /%(%|[0-9a-fA-F][0-9a-fA-F])/)
 184         fi = 1
 185         theformat = fmts[fi]
 186         fpos = length(theformat) + 1
 187         while (fpos <= length(matchfmt)) {
 188                 pct = tolower(substr(matchfmt, fpos, 3))
 189                 if (substr(pct, 1, 2) == "%%") {
 190                         theformat = theformat "%"
 191                         fpos += 2
 192                 } else {
 193                         hexval = (index("0123456789abcdef", substr(pct, 2, 1)) - 1) * 16
 194                         hexval += index("0123456789abcdef", substr(pct, 3, 1)) - 1
 195                         theformat = theformat sprintf("%c", hexval)
 196                         fpos += 3
 197                 }
 198                 if (fi <= fc) {
 199                         theformat = theformat fmts[++fi]
 200                         fpos += length(fmts[fi])
 201                 }
 202         }
 203 }
 204
 205 pckdrefs && $2 ~ /^refs\/./ &&
 206 $1 ~ /^[0-9A-Fa-f][0-9A-Fa-f][0-9A-Fa-f][0-9A-Fa-f]+$/ {
 207         r = $2
 208         sub(/\/+$/, "", r)
 209         refs[++cnt] = r
 210         hashes[cnt] = tolower($1)
 211 }
 212
 213 !pckdrefs && $1 ~ /^refs\/./ &&
 214 $2 ~ /^[0-9A-Fa-f][0-9A-Fa-f][0-9A-Fa-f][0-9A-Fa-f]+$/ {
 215         r = $1
 216         sub(/\/+$/, "", r)
 217         refs[++cnt] = r
 218         hashes[cnt] = tolower($2)
 219 }
 220
 221 function cmpkeys(anarray, i1, i2, _k1, _k2, _ans) {
 222         _ans = 0
 223         if (dosortobj) { # ** cough **
 224                 _k1 = hashes[i1]
 225                 _k2 = hashes[i2]
 226                 if (_k1 < _k2) _ans = -1
 227                 else if (_k1 > _k2) _ans = 1
 228                 if (sortobj < 0) _ans = 0 - _ans
 229         }
 230         if (!_ans) {
 231                 _k1 = anarray[i1]
 232                 _k2 = anarray[i2]
 233                 if (_k1 < _k2) _ans = -1
 234                 else if (_k1 > _k2) _ans = 1
 235                 if (sortref < 0) _ans = 0 - _ans
 236         }
 237         return _ans
 238 }
 239
 240 function formatline(rname, oname, _out) {
 241         _out = theformat
 242         gsub(/%\(objectname\)/, oname, _out)
 243         gsub(/%\(objecttype\)/, "object", _out)
 244         gsub(/[&]/, "\\\\&", rname)
 245         gsub(/%\(refname\)/, rname, _out)
 246         return _out
 247 }
 248
 249 END {
 250         multisort = 1
 251         presortedbyrefonly = 0
 252         if (!dupesok || patcnt > 1 || patarr[1] != "refs/") {
 253                 savesortref = sortref
 254                 sortref = 1
 255                 if (cnt > 1) kasort_partition(refs, 1, cnt)
 256                 presortedbyrefonly = 1
 257                 ji = 1
 258                 ref = ""
 259                 curpat = patarr[ji]
 260                 for (i = 1; i <= cnt; ++i) {
 261                         refs_i = (refs[i] != "") ? refs[i] "/" : ""
 262                         if (refs_i == ref) {
 263                                 refs[i] = ""
 264                                 continue
 265                         }
 266                         ref = refs_i
 267                         if (ref < curpat) {
 268                                 refs[i] = ""
 269                                 continue
 270                         }
 271                         if (substr(ref, 1, length(curpat)) == curpat) continue
 272                         do
 273                                 ++ji
 274                         while (patarr[ji] < substr(ref, 1, length(patarr[ji])))
 275                         curpat = patarr[ji]
 276                         ref = ""
 277                         --i
 278                 }
 279                 sortref = savesortref
 280         }
 281         dosortobj = sortobj
 282         if (cnt > 1 && (!presortedbyrefonly || sortobj || sortref < 0))
 283                 kasort_partition(refs, 1, cnt)
 284         outcnt = 0
 285         for (i = 1; i <= cnt; ++i) {
 286                 refname = refs[i]
 287                 if (refname == "") continue
 288                 if (maxout > 0 && ++outcnt > maxout) exit 0
 289                 objname = hashes[i]
 290                 print formatline(refname, objname)
 291         }
 292 }