Git Repository via Apache

CakePHP, one of the projects I work with, uses Git. I’ve always ever used Subversion personally, so it seems time to get with the program here by setting up a Git repository. Well, Git is a different animal, enabling a distributed workflow, and you don’t have to use it like you use Subversion, but that’s another story.

In short, we’ll create a bare repository to be hosted via HTTP/DAV on Apache.

Solution

Here are the steps I took on Ubuntu 9.10. I had Git installed and an existing Apache server up and running but didn’t have DAV configured.

Start by creating a bare repository by cloning an existing git project like so:

git clone --bare /path/to/git/project /path/to/new/repo.git

Enable access to the repository:

touch /path/to/new/repo.git/git-daemon-export-ok

Copy the repository into place to be served by Apache:

mv /path/to/new/repo.git /var/www/repo.git

Also don’t forget to do this, otherwise gitting stuff doesn’t work:

cd /var/www/repo.git
git --bare update-server-info

If you haven’t set up the Dav module for Apache, you’ll need to if you want to push stuff, etc. Here’s how:

# enable the dav module + dependencies
a2enmod dav_fs

In /etc/apache2/sites-available/default, add a Directory container in the VirtualHost:

<Directory /path/to/repo.git>
   Dav On
   Allow from all
</Directory>

Restart the server…

/etc/init.d/apache2 restart

…and test it out.

Troubleshooting

I hadn’t set up DAV properly and spent an hour figuring out this error when I tried a git push:

error: Cannot access URL http://localhost/atsui/taspa.git/, return code 22
error: failed to push some refs to 'http://localhost/atsui/taspa.git'

It confused me because I could do git clone from the server without trouble, so I didn’t quite know what to think. Checking the log is always a wise thing to do. From Apache’s access.log:

27.0.0.1 - - [19/Jan/2010:09:43:49 -0800] "PROPFIND /atsui/taspa.git/ HTTP/    1.1" 405 565 "-" "git/1.6.3.3"

The 405 HTTP code translates to “Method not allowed”. Although I had enabled the DAV module, I didn’t have DAV enabled on that directory. Follow the steps above and you shouldn’t see the problem.

Thoughts

If you notice, the directory is configured to allow git read/write access to everyone. An extension to this guide might be to set up user authentication on Apache. Or if you’re into SSH and keys, you can set that up, too. I’m not so familiar with that so I might try that out as well.

Git’s got some stuff to get used to. I only found out about bare repositories after trying to push changes to a repository that I cloned from, which is bad because it’s like shoving changes into someone else’s workspace and confusing Git in the process. I’ll have to read more about this workflow. Do people just pull stuff that they like from others? Or should it be that people use Git to create patches and give it to someone to put together?

Links

Here’s the useful references I used for this write-up.

1. http://www.kernel.org/pub/software/scm/git/docs/user-manual.html#setting-up-a-public-repository
   Here’s where I found out how to create a Git repository to use in the Subversion repository style.
2. http://www.kernel.org/pub/software/scm/git/docs/howto/setup-git-server-over-http.txt
   Details on how to get the Git repository onto Apache
3. http://www.jedi.be/blog/2009/05/06/8-ways-to-share-your-git-repository/
   Lots of alternative setups and considerations for choosing specific ones.

C/C++ declarations – no sweat

Pop quiz: how do you declare a reference to an array of pointers to characters in C++?

Well, that’s what I struggled with for a while last night; it is one of the problems in Stroustrup’s big book of C++, except not really: the question asks for an array of pointers to ints and a reference to a pointer to character, but a quick glance made me blend the two together to make some crazy declaration. Well, it still makes sense, and it’s doable:

char *(&refToCharPtrArray)[]

Not too bad, eh? I think the trick to figuring it out is to start from the middle – that is, the variable name – and work your way outwards. So for example, refToCharPtrArray is a reference. What is it referring to? Stepping out one level of parens, it’s clear that we have an array of char pointers. Not too shabby!

At that moment, I felt that I really understand the crazy grammar of declarations, but still, how do you check your answer? The best that I could muster that night was the C++ function typeid, which requires the <typeinfo> header. Basically, you throw the function an expression of some kind and it spits out the type. So this…

char *charPtrArray[] = { "A", "String", "Array" };
char *(&refToCharPtrArrayMaybe)[3] = charPtrArray;
cout << typeid(refToCharPtrArrayMaybe).name() << endl;

Outputs…

A3_Pc

Even the typeid name required some careful reading! Luckily, it’s not as bad as breaking down a nasty declaration, and the results confirm the answer: an array (3) of pointers to chars. The thing is, references can never be gotten at after they are declared. But it does seem to work if you factor in the way references work.

But if you’ve got the terminal handy, you can do even better! There’s a utility called cdecl that is meant for this job, as expressed in the help text:

cdecl> help
...
command:
...
explain <gibberish>
...
gibberish: a C declaration, like 'int *x', or cast, like '(int *)x'


It also goes the other way and you can ask it for a declaration:

c++decl> declare dat as reference to array of pointer to char
Warning: Unsupported in C++ -- 'Reference to array of unspecified dimension'
(maybe you mean "reference to object")
char *(&dat)[]


Though I guess it’s up to whoever works with this magic daily to know it well, it’s nice to know that the tools are there that are meant to help you get the job done, too.

–

Coming soon: Man, that Starcraft AI competition looks wicked!

More on GRUB 2

Yesterday, I was complaining about a little hitch I ran into with the new GRUB bootloader. Today, I found a nice guide is posted here: http://ubuntuforums.org/showthread.php?t=1195275

The days of handwriting grub menus is over: scripts found in /etc/grub.d/ automate detection of new kernels and alternate OS installations. If there’s something unwanted, just chmod -x the script that you don’t want and let the update_grub command take care of generating the ones you do. You can also put custom entries in 40_custom.

So at this point, I still don’t have a nice Tux icon for booting into Linux, but at least I don’t have to hit the down arrow 8 times to choose the operating system I want to boot into

Other mentions:

• GIMP has a single window interface now!?
• Man, C++ declarations are tricky…

New Year’s Reformat

I reformatted my Macbook (2+ years old now) and am bringing back my triple boot configuration, this time with a more intelligent disk partitioning: 50 GB for Ubuntu (9.10), 10 GB for Windows XP (Pro SP2), and the remaining 20 GB for OS X (10.4).

The initial installation of OS X took about an hour to finish, using two DVDs. It used up 16 GB; definitely not a minimal installation. I junked some of the applications like Garageband and iDVD and it freed up about 8 GB, more than enough to allow Software Update to do the job. Two rounds of updates was enough to bring OS X up to date. At this point, though, there are more and more apps that demand at least OS X 10.5, which makes me wonder how much I’ll be playing in OS X from now on.

Next I installed rEFIt. I got the dmg and ran the mpkg, then I popped open a terminal, drilled down to /efi/refit and ran ./enable.sh. Upon restart, the rEFIt menu comes up as usual.

The OS X Disk Utility never makes a working FAT32 partition. As usual, I have to use the XP tool to format before installing, otherwise I get a disk error when booting into XP. After booting into XP, I installed the Macbook drivers generated from Boot Camp that gets the keyboard/touchpad/wireless/etc all squared away, and it did it without crashing, which is always nice. Also remembered to disable the ACPI driver as it can lead to CPU running haywire for no apparent reason.

Installing Ubuntu came last. It installed GRUB (version 2 at this point) in the default location on the MBR, so when I went back into the rEFIt menu, it still showed OS X and XP as the only choices but choosing XP takes you into the GRUB menu. The good thing is that the installer discovers XP and automagically added it to the boot menu. The daisy-chained EFI and GRUB menus are less than ideal, but it doesn’t seem possible to get Linux visible on the EFI boot menu. The way to do it is to install GRUB on the Linux partition rather than on the MBR and doing so makes Tux show up in rEFIt, but I couldn’t get Linux to boot from there. It *might* work with the old GRUB, but I guess it’s more trouble to go against what’s upstream. A little annoying, but everything else works great out of the box.

In conclusion, it’s a great feeling to be able to get a laptop to triple boot in a day’s time, and I’m satisfied with the breathing room of a clean HD and the confidence that I can get anything done on it. Definitely owe a lot to the development that’s happened over the last two years especially on the Linux side. The weeks spent on getting things working on the Macbook with Gentoo was definitely an amazing experience but ever since the X update midway through last semester, the feel was not the same. I learned a lot from the time I spent keeping that system in one piece for so long, and those skills will come in handy this year. Nothing like starting with a clean slate!

Knight’s Tour Problem

A knight's tour

One of the homework problems we had in graph theory class asks the question: given a Knight piece and an 8×8 chessboard, can you start the Knight off on one square, move into every other square once and exactly once, and land back on the square that you started with? This is a really annoying problem because it’s easy to understand and sucks you in for hours. I only got half credit on it by trying to fill a 4×4 part of the board as much as I could and copying the same moves 4 times.  Apparently, a Knight’s tour doesn’t exist for a 4×4 as Professor So mentions some theorems about this problem. If you’re interested in more, check out Schwenk’s theorem.

Coincidentally, I was randomly practicing programming problems in Topcoder and I found that the Knight’s Tour makes an appearance as the 2nd problem in division 2, SRM 447. The problem has you implement an algorithm, namely Warnsdorff’s algorithm, which is a heuristic algorithm that makes the Knight piece walk the board, and if you start with a fresh board with the Knight in a corner, you can actually discover a Knight’s tour. BUT, the thing is, it doesn’t give you the elusive Hamiltonian circuit but rather a Hamiltonian path ie. the starting and ending points that you find with this algorithm are different. Still, it’s pretty awesome for a 500 point problem.

The cool thing about that algorithm is that although the Hamiltonian path problem is NP-hard, it supposedly is able to find Hamiltonian paths in many graphs in linear time. I’ve attached my Java program if you just want to test it out. Don’t worry about having seen this tour and having the problem being spoiled; apparently, there are billions of possible tours. Also, I have not found the Hamiltonian circuit yet, so good job if you managed to find it but don’t tell me

KnightsTour.java

Matrix pivoting in Javascript

I know, it’s a ridiculous idea to write up a scientific computing algorithm that has cubic complexity and is heavy in floating point operations in Javascript, and making it use a randomized function to select the pivot element guarantees that it is completely useless. But it’s got buttons and it’s kinda fun to look at: http://tinyurl.com/gerp143m

Animation is kind of strange to pull off. Scriptaculous has these things called effect queues that let you execute effects in sequence, but what I really needed but couldn’t find was a way to delay execution into intervals and give time for some animation to happen. Or I was thinking of doing all the computation up front and making a queue of the intermediate states to be animated independently and more smoothly after all the math had been worked out. I think that a friend of mine’s semester project actually makes use of some animator model to illustrate class diagrams in Java, with there being some function that takes an arbitrary linked list of actions to execute in sequence. Would’ve been nice to have some time to figure that out.

I ended up using setTimeout to call a function on each row of the matrix with a fixed delay. This is most likely less than ideal because in order to make it work, I had to invoke the method on the object from the global scope rather than something nice. Like what? I don’t know. I had the urge to just pass a function that has the this pointer pointing to the object. I was also wondering about passing the member function to setTimeout, but that felt awkward to even think about.

Features I’d include if I had more time would be a way to input your own matrix of values and an easy way to select the pivot strategy to use on the fly.

BAD Math Day Weekend

I attended yet another BAD Math Day (Bay Area Discrete Math meeting) today. I’ve probably been to four of these, and each time I’ve been equally left in the dust in terms of comprehending anything any speaker says, the best moments being when the speaker mentions a definition that is partially familiar to me from past/current coursework and when the speaker jokingly takes two minutes to remind the “one person in the room” (\me smiles) who doesn’t know of some presumably elementary math concept. So there was nothing out of the ordinary this time.

I think the one thing that stuck to me most was the talk given by the guy from Lawrence Livermore Labs, which introduced me to a bit of game theory in the form of Stackelberg and Nash games, and we also saw some of the algorithms for solving the related optimization problems, with familiar sounding techniques like branch and bound being mentioned. The guy was giving a talk on how counterterrorists and terrorists play this game of trying to one-up the other with probabilities associated to decisions like target area of attack, mode of attack, and all these parameters that sound like you could have a whole lot of fun writing a simulation for, possibly in the form of a Civilization scenario.

Since I didn’t really get much out of it as far as content goes, I paid attention to what I could do as a human being, which is to watch for examples of good speech making. I’m pretty jealous of skilled speakers in general: it is a nontrivial thing to be able to sustain a presentation that makes sense and keeps people paying attention, both for much longer than 5 minutes. The linear optimization guy who talked about computational complexity this time around was skipping tons of slides to get through everything in 30 minutes. You could tell that he knew how much he had to talk about and you’d feel like you could follow as he led you along. Smooth delivery like that can only mean having given that talk a bunch of times before. Of course there was also the not-so-good parts as I guess is to be expected after letting x number of scientists/mathematicians on stage. I think nervousness is pretty transparent on the speaker.

So besides wishing that someday I can possibly understand a little more in these talks, I am wishing that I might make more sense when I talk out loud as well. I’m in for the general GRE this coming week, and I’m putting an honest effort in preparing for that essay part. Screw the vocab, though.

Optical flow on plasma pong

This is long overdue. Plasma Pong is cool because of its physically accurate fluid dynamics, and the idea of determining the flow lines from observing the video with OpenCV is awesome.

The demo code that I modified to make the video is here:

http://robotics.stanford.edu/~dstavens/cs223b/

Also, the original video, which is probably more enjoyable, is here:

http://www.youtube.com/watch?v=NDjseVmruH8

The quest for menu items

For the past few weeks I’ve been working up a sweat over getting an AJAX menu item manager up and running in CakePHP. After much fussing with tweaking the drag-and-drop behavior and a redo of the behind-the-scenes representation in the database, I finally got it to the point where I’m pretty proud of it. That navigation bar with nested menus that you see on some websites? I made that possible, and I made a nice interface to manage it. If you think of how you can organize files and folders on a desktop, you’re not far off from what I have. Today, I’ll just talk about the data structure part of things. Next time, I’ll talk about tying it all up with AJAX.

There’s a little saying in computer science that by picking the right data structure, the rest of the program writes itself. So early on we had the Menu, which in turn has many Menu Items. It’s pretty to create your standard add/edit/delete interface with these things. But the trouble started when we tried putting submenus into menus.

So obviously, that’s opening a can of worms since suddenly you have to worry about not only linking the menus together in a parent-child relationship, but the order of children have to be preserved as well. Well, when editing a menu with the standard form interface to manage this relationship, we have to be careful not to allow infinite recursion by letting the user, say, set a menu’s parent to be one of its children submenus. A simple search to eliminate those children as possibilities did the trick. (By the way, WordPress doesn’t bother to do this with post categories. You can try to set a subcategory to be its own parent’s parent, and it will actually say it updated, but it won’t actually do anything.)

But that was a little ugly in the first place as it doesn’t really show off the hierarchical relationships very well. You could assert that the menus were always connected in a sane manner, but there’s not much to be said if all you have is a select box. What was clear was that a drag-and-drop interface would provide much better feedback about the hierarchy and give a nice overall view of the data. We ended up with an ordered list (actually it’s an ul… forgiveness for the bad semantics!) of list items, which could either be menus or menu items. I will talk about the AJAX portion later this week.

Well, it took a round of writing the update function, which ran up to about 170 lines of PHP, to realize that having a Menu around wasn’t contributing any utility at all. We really were only using it as a key for joining menu items, and it was doing a poor job at that since we incur overhead (unnecessary database queries as well as brainpower) keeping menu items and menus in-sync. Also, we didn’t have to worry about crazy parent relationships popping up because the sanity check is built into a drag-and-drop menu: it becomes impossible drag a parent into its child, therefore, the problem is solved.

So order is kept by giving each menu item a rank. It resulted with a lot of bookkeeping to keep it nice and normalized, going from 1, 2, 3, … N for an N-long menu. Actually, there were only two classes of actions to worry about: insertion/deletion and permutation in the menu. It was around the time that I got the rank fixup working perfectly that I discovered an alternate data structure not involving ‘parent’ and ‘rank’ fields but ‘left’ and ‘right’. This alternate structure is called the Nested Set, as opposed to the Adjacency List model that I ended up with. The Nested Set is something I would never have ‘come up with on my own’ unless I knew about it, but it’s very impressive, bragging O(1) on the number of queries it takes to retrieve menus (whereas with the adjacency list, this is dependent on the depth of the menu). However, the complexity of updating rank with nested sets is equal to or greater than keeping track of rank in the adjacency list model.

The good news is that CakePHP provides a built-in Behavior to handle this. The bad news it seems incomplete and not very well documented. I’d recommend looking into this just because it seems impressive on the way it handles primitive operations and also because it seems like the ‘proper’ way to do things. I don’t want to, at this point, just because I have twice-rewritten code that already works fine!

Oh man, it’s August already

Sorry for not posting more. I’ve got a couple of posts lined up for publish later this week (I need deadlines to get anywhere): one about developments in a computer vision project using OpenCV, the other about some AJAX’y antics in CakePHP worth mentioning. In the meantime, I randomly drew this from fortune earlier last week, taken from the work of one resident SJSU professor we all love:

Cosmotronic Software Unlimited Inc. does not warrant that the functions contained in the program will meet your requirements or that the operation of the program will be uninterrupted or error-free. However, Cosmotronic Software Unlimited Inc. warrants the diskette(s) on which the program is furnished to be of black color and square shape under normal use for a period of ninety (90) days from the date of purchase.

NOTE: IN NO EVENT WILL COSMOTRONIC SOFTWARE UNLIMITED OR ITS DISTRIBUTORS AND THEIR DEALERS BE LIABLE TO YOU FOR ANY DAMAGES, INCLUDING ANY LOST PROFIT, LOST SAVINGS, LOST PATIENCE OR OTHER INCIDENTAL OR CONSEQUENTIAL DAMAGES.

— Horstmann Software Design, the “ChiWriter” user manual