Musings of a Software Engineering Student

I’ve recently gotten involved in the emacs development community. I’m not a commiter or anything, but I’m working on improving Java support for cc-mode, have a lrage patch(that is unfortunately currently in limbo), and have been submitting bugfixes for problems I’ve been running into. This post describes the fixes for a few of these bugs that you can add to your emacs configuration and fix right now.

The first patch is to dirtrack. If you have a somewhat incorrectly-specified regexp for your shell, dirtrack will sometimes eat output from your shell buffer and error out. Specifically, this happens when a non-existent directory is matched. This is clearly not what you want; instead, in most cases I want dirtrack to just ignore this, not switch the buffer, and proceed as normal. The following function does this, although it still messages you about an incorrect match:

(defun dirtrack (input)
  "Determine the current directory by scanning the process output for a prompt.
The prompt to look for is the first item in `dirtrack-list'.
 
You can toggle directory tracking by using the function `dirtrack-mode'.
 
If directory tracking does not seem to be working, you can use the
function `dirtrack-debug-mode' to turn on debugging output."
  (unless (or (null dirtrack-mode)
              (eq (point) (point-min)))     ; no output?
    (let (prompt-path
          (current-dir default-directory)
          (dirtrack-regexp    (nth 0 dirtrack-list))
          (match-num	      (nth 1 dirtrack-list))
          ;; Currently unimplemented, it seems.  --Stef
          (multi-line	      (nth 2 dirtrack-list)))
      (save-excursion
        ;; No match
        (if (not (string-match dirtrack-regexp input))
            (dirtrack-debug-message
             (format "Input `%s' failed to match `dirtrack-list'" input))
          (setq prompt-path (match-string match-num input))
          ;; Empty string
          (if (not (> (length prompt-path) 0))
              (dirtrack-debug-message "Match is empty string")
            ;; Transform prompts into canonical forms
            (setq prompt-path (funcall dirtrack-directory-function
                                       prompt-path)
                  current-dir (funcall dirtrack-canonicalize-function
                                       current-dir))
            (dirtrack-debug-message
             (format "Prompt is %s\nCurrent directory is %s"
                     prompt-path current-dir))
            ;; Compare them
            (if (or (string= current-dir prompt-path)
                    (string= current-dir (abbreviate-file-name prompt-path)))
                (dirtrack-debug-message (format "Not changing directory"))
              ;; It's possible that Emacs will think the directory
              ;; won't exist (eg, rlogin buffers)
              (if (file-accessible-directory-p prompt-path)
                  ;; Change directory
                  (and (shell-process-cd prompt-path)
                       (run-hooks 'dirtrack-directory-change-hook)
                       (dirtrack-debug-message
                        (format "Changing directory to %s" prompt-path)))
                (progn (message "Directory %s does not exist" prompt-path) input)))
            )))))
  input)

Another small patch is to python.el’s syntax highlighting. In the current form, def and class are only highlighted as keywords when the function/class name is started. This is clearly wrong, and led to me spending a few minutes looking up python method declaration syntax, as it looked like ‘def’ wasn’t a keyword. To fix this, put this in your .emacs file:

 
    (,(rx symbol-start "None" symbol-end)	; see � Keywords in 2.5 manual
     . font-lock-constant-face)
    ;; Definitions
    (,(rx symbol-start (group "class") (? (1+ space) (group (1+ (or word ?_)))))
     (1 font-lock-keyword-face) (2 font-lock-type-face))
    (,(rx symbol-start (group "def") (? (1+ space) (group (1+ (or word ?_)))))
     (1 font-lock-keyword-face) (2 font-lock-function-name-face))
    ;; Top-level assignments are worth highlighting.
    (,(rx line-start (group (1+ (or word ?_))) (0+ space) "=")
     (1 font-lock-variable-name-face))
    ;; decorators
    (,(rx line-start (* (any " \t")) (group "@" (1+ (or word ?_ ?.))))
     (1 font-lock-type-face))
    ;; Built-ins.  (The next three blocks are from
    ;; `__builtin__.__dict__.keys()' in Python 2.5.1.  Now modified
    ;; for Python 2/3 compatibility.)  These patterns are debateable,
    ;; but they at least help to spot possible shadowing of builtins.
    (,(rx symbol-start (or
                        ;; exceptions
                        "ArithmeticError" "AssertionError" "AttributeError"
                        "BaseException" "DeprecationWarning" "EOFError"
                        "EnvironmentError" "Exception" "FloatingPointError"
                        "FutureWarning" "GeneratorExit" "IOError" "ImportError"
                        "ImportWarning" "IndentationError" "IndexError" "KeyError"
                        "KeyboardInterrupt" "LookupError" "MemoryError" "NameError"
                        "NotImplemented" "NotImplementedError" "OSError"
                        "OverflowError" "PendingDeprecationWarning" "ReferenceError"
                        "RuntimeError" "RuntimeWarning" "StandardError"
                        "StopIteration" "SyntaxError" "SyntaxWarning" "SystemError"
                        "SystemExit" "TabError" "TypeError" "UnboundLocalError"
                        "UnicodeDecodeError" "UnicodeEncodeError" "UnicodeError"
                        "UnicodeTranslateError" "UnicodeWarning" "UserWarning"
                        "ValueError" "Warning" "ZeroDivisionError") symbol-end)
     . font-lock-type-face)
    (,(rx (or line-start (not (any ". \t"))) (* (any " \t")) symbol-start
          (group (or
                  ;; callable built-ins, fontified when not appearing as
                  ;; object attributes
                  "abs" "all" "any" "bool"
                  "chr" "classmethod" "cmp" "compile" "complex"
                  "copyright" "credits" "delattr" "dict" "dir" "divmod"
                  "enumerate" "eval" "exit" "filter" "float"
                  "frozenset" "getattr" "globals" "hasattr" "hash" "help"
                  "hex" "id" "input" "int" "isinstance" "issubclass"
                  "iter" "len" "license" "list" "locals" "map" "max"
                  "min" "object" "oct" "open" "ord" "pow" "property" "quit"
                  "range" "repr" "reversed"
                  "round" "set" "setattr" "slice" "sorted" "staticmethod"
                  "str" "sum" "super" "tuple" "type" "vars"
                  "xrange" "zip")) symbol-end)
     (1 font-lock-builtin-face))
    (,(rx symbol-start (or
                        ;; other built-ins
                        "True" "False" "Ellipsis"
                        "_" "__debug__" "__doc__" "__import__" "__name__") symbol-end)
     . font-lock-builtin-face)))

The last small patch is a fix for vc-revert-file. Right now, if you have a split window and call vc-revert-file, your other window will be closed in the process of reverting the file. This is clearly wrong; the following function replaces vc-revert-file to leave your window configuration alone after reverting the file.

I’ve been using c-eldoc-mode, the C plugin for eldoc, on and off for some time now. On one hand, the functionality of eldoc is amazing; it is very nice to have function signatures displayed in the echo area when you are in the argument list. When making function calls, you can easily ensure that you are putting arguments in the right order; when reading code, you can tell what the arguments correspond to. However, c-eldoc.el was quite slow on larger codebases such as the emacs source code; each movement command could halt processing for up to a second, which is completely unacceptable.

I decided to see what I could do to speed it up. On reading the source code, I found the main problem; for each lookup, the C preprocessor was called on the file, and grep was called on the results. While the ability to use grep, speeding up regex lookups, was the original point of doing this, in a a large project running the C preprocessor so much would completely kill performance. The easiest way to fix this was just to cache the C preprocessor output for some amount of time; in my case, I decided regenerating the buffer every 120 seconds was good enough. After implementing this, performance was greatly enhanced, and I haven’t had any performance problems so far; if you still are, please let me know, preferably with some details of how large the preprocessor output is.

Mostly, the improvements of c-eldoc involved caching the results of running the c preprocessor, instead of running it on each symbol change. For this, I wanted a cached hash table; one where the key-value pairs would expire after some amount of time. Since Emacs does not have one of these built in, and it is a general enough concept that I may need it outside of c-eldoc, I wrote the cache in it’s own library. c-eldoc still contains the cache code, as I didn’t want to annoy users of it, but the cache is also available standalone.

cache.el, which you can download here, currently provides only three functions; cache-make-cache, cache-gethash, and cache-puthash. Three arguments are provided to cache-make-cache, as well as the key arguments that are also given to make-hash-table; an initialization function, a test function, and a cleanup function. The initialization function is called with no arguments when a value is first put into the cache; the value it returns is stored along with the value put into the cache. The test function is called when a value is retrieved; It is passed the previously computed value of the initialization function, and returns t if the value has expired. If so, the key-value pair is removed from the hash table, and the cleanup function is called with the value of the key-value pair.

The cache structure is designed to emulate the hash tables of emacs as much as possible: there is no difference in interface or semantics of return value between cache-gethash and gethash, or cache-puthash and puthash. Additionally, all key arguments to make-hash-table can also be passed to cache-make-cache, and are used in the hash table backing the cache.

The cache data structure is just a list of a hash table and the three functions passed to cache-make-cache; this allows all the normal hash functions to be called on the car of the result returned by cache-make-cache. I believe that this will suffice without much irritation; however, if the lack of some utility does make the cache more difficult to use, please tell me and I will implement them.

While working on my raytracer, I became curious as to what the dependency graph of my code looked like. To accomplish this, I wrote a Python script that will scan a given directory and generate the dependency graph as a PDF file. This graph can either help you find unnecessary dependencies, locate circular dependencies, or just satisfy your curiosity.




This script requires both Python 2.6 and dot. If you are running Ubuntu, you can install dot with:

sudo apt-get install graphviz

Running the script with python is done as follows:

python cppdepends.py dir outfile

Where dir contains the source tree you wish to generate a graph for, and outfile is the pdf file you wish to output to.

This program is located at http://github.com/nflath.cppdepends. If you have any suggestions or improvements, or even if you just used it, please let me know.

A while ago, I released save-visited-files-mode, a mode I wrote to keep files open between Emacs sessions. A few people including me have been using it since then; I’ve written about it before here and here. A few weeks ago, Jonathan Kotta emailed me a patch that fixed a few minor issues, as well as cleaned up the code. After applying the patch, I’m now releasing version 1.2. The changes from version 1.1 are as follows:

• Changed the default location of the persistence file so a new directory doesn’t have to be created.
• Makes sure that save-visited-files-location is writable; if not, displays an error.
• Doesn’t print a message every time it saves the file list.
• Miscellaneous code cleanup.

I’ve also moved save-visited-files-mode.el to a github repository, located at http://github.com/nflath/save-visited-files.This is a much better solution than keeping a copy just in my emacs customization subversion, since I am distributing this as a stand-alone project. I’ll continue posting updates here, as well, but the source will be committed to that repository.

I’ve started playing around with CUDA, attempting to make a ray-traced pacman clone. Instructions for how to set up the CUDA SDK on Ubuntu are located at http://lifeofaprogrammergeek.blogspot.com/2008/05/cuda-development-in-ubuntu.html; There were a few others instructions that I tried that didn’t end up working. As a note to all of you on Ubuntu 9.10: CUDA does not work with the version of GCC that comes with Ubuntu 9.10. To be able to do CUDA development, you need to downgrade your GCC version to 4.3.

Once the SDK is set up, you can start coding for CUDA. The most useful documents for helping me do this so far have been the CUDA Programming Guide, NVidia’s official guide and reference manual to CUDA, and Dr. Dobb’s CUDA: Supercomputing from the Masses. These have been enough to get me started; currently, my Pacman clone is having some memory issues that causes my program to work in device emulation mode, but I’ve gotten their simpler examples working and understand the basics.

For editing CUDA files, I use cuda-mode. This is an extension to c-mode that provides syntax highlighting for the new constructs, such as __device__ and __global__. It doesn’t do much else, but CUDA shares enough syntax(virtually all of it) with C so that cc-mode is sufficient for editing it. Once you’ve added cuda-mode.el to your load-path, all you have to do to enable it is add the following to your initialization file:

(require 'cuda-mode)

Languages Matter
http://www.youtube.com/watch?v=ix2DeCzuckc

The world is driven by computers, but most people don’t love them -
they consider them mere tools. The people who love computers,
programmers, are the ones who change the world. Languages matter,
since all software is written in some language, and computers don’t
work without software.

Similarly to the issue with computers, most programmers don’t love
languages. However, languages are important to programmers - they help programmers think, five inspiration, and affect productivity. Different languages will enlighten programmers in different ways - BASIC did not teach me recursion.

In summary, you should be happy using a language.

I’ve ben doing a decent amount of C and C++ coding recently - both for courses and for hacking on emacs. I ended up doing a bit of work on my C configuration, though probably not as much as I should.

Part of these efforts included improving h-file-create, the function that is automatically run whenever I create a new header file. Previously, it only created the #ifndef guards; While these are the only things I’ll always need, the vast majority of time I also wanted to define a class, and so I programmed the class to be inserted automatically.

(defun h-file-create ()
  "Create a new h file.  Insert a infdef/define/endif block"
  (interactive)
  (if (or (equal (substring (buffer-name (current-buffer)) -2 ) ".h")
          (equal (substring (buffer-name (current-buffer)) -4 ) ".hpp"))
      (let* ((buffer-name (buffer-name (current-buffer)))
             (class-name (substring buffer-name 0 (string-match "\\." buffer-name))))
      (when (equal "" (buffer-string))
          (insert "#ifndef "
                  (upcase class-name)
                  "_H\n#define "
                  (upcase class-name) 
                  "_H\n\nclass "
                  (capitalize class-name)
                  " {\npublic:\n\n\nprivate:\n\n\n};"
                  "\n\n#endif")
        (search-backward "public:\n")
        (next-line)))))

Another function I ended up needing was to insert includes to header files or forward declarations of classes. Previously, I’d have to go to the top of my file, interrupting whatever I was doing, and maneuver back. This was just an annoyance, so I wrote the following functions that would either include or forward declare something, defaulting to the current word at point. Since whether I #included or forward declared often depended on whether I was in a header or implementation file, so I wrote another function that delegates to one of the other two depending on which file you were in. String-match-any is a utility function I wrote to help do this.

(defun string-match-any (regexp-list string &optional start)
  "Returns whether the given string, starting at position start,
matches any regexp in the list"
  (if regexp-list
      (let ((result (string-match (car regexp-list) string start)))
            (if result
                result
              (string-match-any (cdr regexp-list) string start)))))
 
(defun-my c-include
  (interactive)
  (save-excursion
    (goto-char (point-min))
    (if (search-forward "#include" nil t)
        (progn (beginning-of-line)
               (insert (concat "#include \"" (downcase arg) ".hpp\"\n")))
      (search-forward "\n\n")
      (insert "#include \"" (downcase arg) ".hpp\"\n\n"))))
 
(defun-my c-forward-declare
  (interactive)
  (save-excursion
    (goto-char (point-min))
    (if (re-search-forward "class [a-zA-Z]*;" nil t)
        (insert (concat "\nclass " (capitalize arg) ";"))
      (search-forward "\n\n")
      (insert "class " (capitalize arg) ";\n\n"))))
 
(defun-my c-fwdinclude
  (interactive)
  (let ((buffer-name (buffer-name (current-buffer))))
    (if (string-match-any (list "\.h" "\.hpp") buffer-name )
        (c-forward-declare arg)
      (c-include arg))))
(define-key c-mode-base-map (kbd "C-c c f") 'my-c-fwdinclude)

I’ve also been using c-eldoc-mode more. It’s pretty awesome, but there is one problem with it: its speed. On a large project like emacs, it will frequently lock the input for some time. It’s useful enough that I’d for it to be faster. If there’s a later version that fixes this that you know of, please tell me; the latest I’ve found is v0.4. Otherwise, I’m going to look into it further to see if I can figure out how to speed it up some more.

As part of the raytracer I wrote for my CS488 (graphics) course, I rendered a pacman scene. This was fun enough that I’ve decided one of my projects over this next work term will be to try and write a real-time raytraced pacman clone, almost certainly using CUDA. I haven’t used CUDA before, so I’ll undoubtedly end up learning a lot. The goal will be to be able to render it at 30FPS on my laptop, which has a NVidia 8500 as a graphics card. I don’t know how feasible this is, but I can try.

While my raytracer had a few performance enhancements, it still took about three minutes to render my final scene. Clearly, this isn’t nearly fast enough, and I don’t think I’ll be able to get anywhere close to necessary on my CPU; an order of magnitude *may* be possible, but certainly not three. The natural solution is to try using the GPU; CUDA seems to be the most popular way of doing this, and I’ve wanted to learn it for a while.

A few additional things I’m going to have to add to my raytracer while porting it to CUDA:
CSG and better KD-Trees, for one. I didn’t end up implementing constructive solid geometry at all, although I have a pretty good idea of how to do that. Unfortunately, it’s going to require a decent amount of refactoring of my raytracer; currently, my Intersection objects only store one intersection point; this will have to change to store ranges of points. I may not have to end up doing this, depending on how much it helps; I’d probably only end up using it to render Pacman, who was a polygon I created using CSG in blender for my project.

The other main optimization I’ll probably have to make is to improve my KD-Trees. I used a good traversal algorithm for my project (Havran’s T_REC_B from his thesis, if you were wondering). However, I use the naive median tree-splitting algorithm instead of implementing SAH. Implementing a correct tree for a scene as complex as a Pac-Man level will probably give me enough of a performance boost that I’ll want to do this properly.

Those are my current concrete plans; I probably won’t be able to work on it very much for the next week or so due to finals, but I may be able to get started. If you know of any good resources, or have any advice, please let me know.

I haven’t had enough time to write a post for the last week, so instead I’ll post a link to the pictures the raytracer I was working on generated.

http://www.student.cs.uwaterloo.ca/~nflath/website