sys/src/cmd/python/Extra/mercurial/parsers.c

   1 /*
   2  parsers.c - efficient content parsing
   3
   4  Copyright 2008 Matt Mackall <mpm@selenic.com> and others
   5
   6  This software may be used and distributed according to the terms of
   7  the GNU General Public License, incorporated herein by reference.
   8 */
   9
  10 #include <Python.h>
  11 #include <ctype.h>
  12 #include <string.h>
  13
  14 static int hexdigit(char c)
  15 {
  16         if (c >= '0' && c <= '9')
  17                 return c - '0';
  18         if (c >= 'a' && c <= 'f')
  19                 return c - 'a' + 10;
  20         if (c >= 'A' && c <= 'F')
  21                 return c - 'A' + 10;
  22
  23         PyErr_SetString(PyExc_ValueError, "input contains non-hex character");
  24         return 0;
  25 }
  26
  27 /*
  28  * Turn a hex-encoded string into binary.
  29  */
  30 static PyObject *unhexlify(const char *str, int len)
  31 {
  32         PyObject *ret;
  33         const char *c;
  34         char *d;
  35
  36         ret = PyString_FromStringAndSize(NULL, len / 2);
  37         if (!ret)
  38                 return NULL;
  39
  40         d = PyString_AS_STRING(ret);
  41         for (c = str; c < str + len;) {
  42                 int hi = hexdigit(*c++);
  43                 int lo = hexdigit(*c++);
  44                 *d++ = (hi << 4) | lo;
  45         }
  46
  47         return ret;
  48 }
  49
  50 /*
  51  * This code assumes that a manifest is stitched together with newline
  52  * ('\n') characters.
  53  */
  54 static PyObject *parse_manifest(PyObject *self, PyObject *args)
  55 {
  56         PyObject *mfdict, *fdict;
  57         char *str, *cur, *start, *zero;
  58         int len;
  59
  60         if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest",
  61                               &PyDict_Type, &mfdict,
  62                               &PyDict_Type, &fdict,
  63                               &str, &len))
  64                 goto quit;
  65
  66         for (start = cur = str, zero = NULL; cur < str + len; cur++) {
  67                 PyObject *file = NULL, *node = NULL;
  68                 PyObject *flags = NULL;
  69                 int nlen;
  70
  71                 if (!*cur) {
  72                         zero = cur;
  73                         continue;
  74                 }
  75                 else if (*cur != '\n')
  76                         continue;
  77
  78                 if (!zero) {
  79                         PyErr_SetString(PyExc_ValueError,
  80                                         "manifest entry has no separator");
  81                         goto quit;
  82                 }
  83
  84                 file = PyString_FromStringAndSize(start, zero - start);
  85                 if (!file)
  86                         goto bail;
  87
  88                 nlen = cur - zero - 1;
  89
  90                 node = unhexlify(zero + 1, nlen > 40 ? 40 : nlen);
  91                 if (!node)
  92                         goto bail;
  93
  94                 if (nlen > 40) {
  95                         PyObject *flags;
  96
  97                         flags = PyString_FromStringAndSize(zero + 41,
  98                                                            nlen - 40);
  99                         if (!flags)
 100                                 goto bail;
 101
 102                         if (PyDict_SetItem(fdict, file, flags) == -1)
 103                                 goto bail;
 104                 }
 105
 106                 if (PyDict_SetItem(mfdict, file, node) == -1)
 107                         goto bail;
 108
 109                 start = cur + 1;
 110                 zero = NULL;
 111
 112                 Py_XDECREF(flags);
 113                 Py_XDECREF(node);
 114                 Py_XDECREF(file);
 115                 continue;
 116         bail:
 117                 Py_XDECREF(flags);
 118                 Py_XDECREF(node);
 119                 Py_XDECREF(file);
 120                 goto quit;
 121         }
 122
 123         if (len > 0 && *(cur - 1) != '\n') {
 124                 PyErr_SetString(PyExc_ValueError,
 125                                 "manifest contains trailing garbage");
 126                 goto quit;
 127         }
 128
 129         Py_INCREF(Py_None);
 130         return Py_None;
 131 quit:
 132         return NULL;
 133 }
 134
 135 #ifdef _WIN32
 136 # ifdef _MSC_VER
 137 /* msvc 6.0 has problems */
 138 #  define inline __inline
 139 typedef unsigned long uint32_t;
 140 typedef unsigned __int64 uint64_t;
 141 # else
 142 #  include <stdint.h>
 143 # endif
 144 static uint32_t ntohl(uint32_t x)
 145 {
 146         return ((x & 0x000000ffUL) << 24) |
 147                ((x & 0x0000ff00UL) <<  8) |
 148                ((x & 0x00ff0000UL) >>  8) |
 149                ((x & 0xff000000UL) >> 24);
 150 }
 151 #else
 152 /* not windows */
 153 # include <sys/types.h>
 154 # if defined __BEOS__ && !defined __HAIKU__
 155 #  include <ByteOrder.h>
 156 # else
 157 #  include <arpa/inet.h>
 158 # endif
 159 # include <inttypes.h>
 160 #endif
 161
 162 static PyObject *parse_dirstate(PyObject *self, PyObject *args)
 163 {
 164         PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;
 165         PyObject *fname = NULL, *cname = NULL, *entry = NULL;
 166         char *str, *cur, *end, *cpos;
 167         int state, mode, size, mtime;
 168         unsigned int flen;
 169         int len;
 170         char decode[16]; /* for alignment */
 171
 172         if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate",
 173                               &PyDict_Type, &dmap,
 174                               &PyDict_Type, &cmap,
 175                               &str, &len))
 176                 goto quit;
 177
 178         /* read parents */
 179         if (len < 40)
 180                 goto quit;
 181
 182         parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);
 183         if (!parents)
 184                 goto quit;
 185
 186         /* read filenames */
 187         cur = str + 40;
 188         end = str + len;
 189
 190         while (cur < end - 17) {
 191                 /* unpack header */
 192                 state = *cur;
 193                 memcpy(decode, cur + 1, 16);
 194                 mode = ntohl(*(uint32_t *)(decode));
 195                 size = ntohl(*(uint32_t *)(decode + 4));
 196                 mtime = ntohl(*(uint32_t *)(decode + 8));
 197                 flen = ntohl(*(uint32_t *)(decode + 12));
 198                 cur += 17;
 199                 if (flen > end - cur) {
 200                         PyErr_SetString(PyExc_ValueError, "overflow in dirstate");
 201                         goto quit;
 202                 }
 203
 204                 entry = Py_BuildValue("ciii", state, mode, size, mtime);
 205                 if (!entry)
 206                         goto quit;
 207                 PyObject_GC_UnTrack(entry); /* don't waste time with this */
 208
 209                 cpos = memchr(cur, 0, flen);
 210                 if (cpos) {
 211                         fname = PyString_FromStringAndSize(cur, cpos - cur);
 212                         cname = PyString_FromStringAndSize(cpos + 1,
 213                                                            flen - (cpos - cur) - 1);
 214                         if (!fname || !cname ||
 215                             PyDict_SetItem(cmap, fname, cname) == -1 ||
 216                             PyDict_SetItem(dmap, fname, entry) == -1)
 217                                 goto quit;
 218                         Py_DECREF(cname);
 219                 } else {
 220                         fname = PyString_FromStringAndSize(cur, flen);
 221                         if (!fname ||
 222                             PyDict_SetItem(dmap, fname, entry) == -1)
 223                                 goto quit;
 224                 }
 225                 cur += flen;
 226                 Py_DECREF(fname);
 227                 Py_DECREF(entry);
 228                 fname = cname = entry = NULL;
 229         }
 230
 231         ret = parents;
 232         Py_INCREF(ret);
 233 quit:
 234         Py_XDECREF(fname);
 235         Py_XDECREF(cname);
 236         Py_XDECREF(entry);
 237         Py_XDECREF(parents);
 238         return ret;
 239 }
 240
 241 const char nullid[20];
 242 const int nullrev = -1;
 243
 244 /* create an index tuple, insert into the nodemap */
 245 static PyObject * _build_idx_entry(PyObject *nodemap, int n, uint64_t offset_flags,
 246                                    int comp_len, int uncomp_len, int base_rev,
 247                                    int link_rev, int parent_1, int parent_2,
 248                                    const char *c_node_id)
 249 {
 250         int err;
 251         PyObject *entry, *node_id, *n_obj;
 252
 253         node_id = PyString_FromStringAndSize(c_node_id, 20);
 254         n_obj = PyInt_FromLong(n);
 255         if (!node_id || !n_obj)
 256                 err = -1;
 257         else
 258                 err = PyDict_SetItem(nodemap, node_id, n_obj);
 259
 260         Py_XDECREF(n_obj);
 261         if (err)
 262                 goto error_dealloc;
 263
 264         entry = Py_BuildValue("LiiiiiiN", offset_flags, comp_len,
 265                               uncomp_len, base_rev, link_rev,
 266                               parent_1, parent_2, node_id);
 267         if (!entry)
 268                 goto error_dealloc;
 269         PyObject_GC_UnTrack(entry); /* don't waste time with this */
 270
 271         return entry;
 272
 273 error_dealloc:
 274         Py_XDECREF(node_id);
 275         return NULL;
 276 }
 277
 278 /* RevlogNG format (all in big endian, data may be inlined):
 279  *    6 bytes: offset
 280  *    2 bytes: flags
 281  *    4 bytes: compressed length
 282  *    4 bytes: uncompressed length
 283  *    4 bytes: base revision
 284  *    4 bytes: link revision
 285  *    4 bytes: parent 1 revision
 286  *    4 bytes: parent 2 revision
 287  *   32 bytes: nodeid (only 20 bytes used)
 288  */
 289 static int _parse_index_ng (const char *data, int size, int inlined,
 290                             PyObject *index, PyObject *nodemap)
 291 {
 292         PyObject *entry;
 293         int n = 0, err;
 294         uint64_t offset_flags;
 295         int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
 296         const char *c_node_id;
 297         const char *end = data + size;
 298         char decode[64]; /* to enforce alignment with inline data */
 299
 300         while (data < end) {
 301                 unsigned int step;
 302
 303                 memcpy(decode, data, 64);
 304                 offset_flags = ntohl(*((uint32_t *) (decode + 4)));
 305                 if (n == 0) /* mask out version number for the first entry */
 306                         offset_flags &= 0xFFFF;
 307                 else {
 308                         uint32_t offset_high =  ntohl(*((uint32_t *) decode));
 309                         offset_flags |= ((uint64_t) offset_high) << 32;
 310                 }
 311
 312                 comp_len = ntohl(*((uint32_t *) (decode + 8)));
 313                 uncomp_len = ntohl(*((uint32_t *) (decode + 12)));
 314                 base_rev = ntohl(*((uint32_t *) (decode + 16)));
 315                 link_rev = ntohl(*((uint32_t *) (decode + 20)));
 316                 parent_1 = ntohl(*((uint32_t *) (decode + 24)));
 317                 parent_2 = ntohl(*((uint32_t *) (decode + 28)));
 318                 c_node_id = decode + 32;
 319
 320                 entry = _build_idx_entry(nodemap, n, offset_flags,
 321                                         comp_len, uncomp_len, base_rev,
 322                                         link_rev, parent_1, parent_2,
 323                                         c_node_id);
 324                 if (!entry)
 325                         return 0;
 326
 327                 if (inlined) {
 328                         err = PyList_Append(index, entry);
 329                         Py_DECREF(entry);
 330                         if (err)
 331                                 return 0;
 332                 } else
 333                         PyList_SET_ITEM(index, n, entry); /* steals reference */
 334
 335                 n++;
 336                 step = 64 + (inlined ? comp_len : 0);
 337                 if (end - data < step)
 338                         break;
 339                 data += step;
 340         }
 341         if (data != end) {
 342                 if (!PyErr_Occurred())
 343                         PyErr_SetString(PyExc_ValueError, "corrupt index file");
 344                 return 0;
 345         }
 346
 347         /* create the nullid/nullrev entry in the nodemap and the
 348          * magic nullid entry in the index at [-1] */
 349         entry = _build_idx_entry(nodemap,
 350                         nullrev, 0, 0, 0, -1, -1, -1, -1, nullid);
 351         if (!entry)
 352                 return 0;
 353         if (inlined) {
 354                 err = PyList_Append(index, entry);
 355                 Py_DECREF(entry);
 356                 if (err)
 357                         return 0;
 358         } else
 359                 PyList_SET_ITEM(index, n, entry); /* steals reference */
 360
 361         return 1;
 362 }
 363
 364 /* This function parses a index file and returns a Python tuple of the
 365  * following format: (index, nodemap, cache)
 366  *
 367  * index: a list of tuples containing the RevlogNG records
 368  * nodemap: a dict mapping node ids to indices in the index list
 369  * cache: if data is inlined, a tuple (index_file_content, 0) else None
 370  */
 371 static PyObject *parse_index(PyObject *self, PyObject *args)
 372 {
 373         const char *data;
 374         int size, inlined;
 375         PyObject *rval = NULL, *index = NULL, *nodemap = NULL, *cache = NULL;
 376         PyObject *data_obj = NULL, *inlined_obj;
 377
 378         if (!PyArg_ParseTuple(args, "s#O", &data, &size, &inlined_obj))
 379                 return NULL;
 380         inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
 381
 382         /* If no data is inlined, we know the size of the index list in
 383          * advance: size divided by size of one one revlog record (64 bytes)
 384          * plus one for the nullid */
 385         index = inlined ? PyList_New(0) : PyList_New(size / 64 + 1);
 386         if (!index)
 387                 goto quit;
 388
 389         nodemap = PyDict_New();
 390         if (!nodemap)
 391                 goto quit;
 392
 393         /* set up the cache return value */
 394         if (inlined) {
 395                 /* Note that the reference to data_obj is only borrowed */
 396                 data_obj = PyTuple_GET_ITEM(args, 0);
 397                 cache = Py_BuildValue("iO", 0, data_obj);
 398                 if (!cache)
 399                         goto quit;
 400         } else {
 401                 cache = Py_None;
 402                 Py_INCREF(Py_None);
 403         }
 404
 405         /* actually populate the index and the nodemap with data */
 406         if (!_parse_index_ng (data, size, inlined, index, nodemap))
 407                 goto quit;
 408
 409         rval = Py_BuildValue("NNN", index, nodemap, cache);
 410         if (!rval)
 411                 goto quit;
 412         return rval;
 413
 414 quit:
 415         Py_XDECREF(index);
 416         Py_XDECREF(nodemap);
 417         Py_XDECREF(cache);
 418         Py_XDECREF(rval);
 419         return NULL;
 420 }
 421
 422
 423 static char parsers_doc[] = "Efficient content parsing.";
 424
 425 static PyMethodDef methods[] = {
 426         {"parse_manifest", parse_manifest, METH_VARARGS, "parse a manifest\n"},
 427         {"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"},
 428         {"parse_index", parse_index, METH_VARARGS, "parse a revlog index\n"},
 429         {NULL, NULL}
 430 };
 431
 432 PyMODINIT_FUNC initparsers(void)
 433 {
 434         Py_InitModule3("parsers", methods, parsers_doc);
 435 }