Wangling

KVO(Key-Value Observing) is a very nice programming facility from Apple. Working together with KVC(Key-Value Coding), it makes the life of Apple developers a lot easier and happier.

However, I recently found some annoying problems of KVO while building some reusable programming components ^(I’ll open source as much as possible when ready.)$ for Voodo and future iOS projects.

Observers can not be queried

Observers are stored in dictionaries ^(See NSKeyValueObserving protocol’s observationInfo.)$, so it should be very easy to query whether an object A is a registered observer of object B. But one can’t do that.

Unregistering an unregistered observer throws exception

One can not query whether A is an observer of B in the first place, and can neither try to unregister it from B when one wants to ensure that A is unregistered from B. It is just ridiculous! And why is removing a nonexistent observer so fatal while removing a nonexistent entry from a collection is reasonably ignored? ^(See NSMutableArray’s removeObject: and NSMutableDictionary’s removeObjectForKey:)$

Observers/observees don’t auto-dissolve the KVO relationship in dealloc

It can be easily done in KVO framework code since it already has the data structure keeping the observer-observee relationship information, and is very reasonable things to do – when any part of a relationship is gone the relationship is ended. Without the auto-unregistration, developers’ responsibility is unnecessarily heavier. In fact, it is no easy work in cases where observers outlive observees, because an observee needs to notify its observers of its death so the observers can detach themselves from the dying observee. ^(Normally it is the observers that are doing the KVO relationship management and it is the job of whoever did the connection to do the disconnection, but vice versa)$

All in all

KVO leaves some extra, tedious, and burdensome relationship management work to us while it could be easily and efficiently done at the root of itself. ^(Well, as Appler eskimo1 said in devforums, it is harder than one might think because KVO needs to be both thread safe and GC clean, and must be careful to not impact the performance of code that isn’t using it.)$

The KVO relationship management is especially stressful for observers watching many dynamic observees which is not unusual for generic components – UINavigationController and UITabBarController both manage a dynamic group of UIViewControllers and may observe some properties of them. It is even worse in my component because not only the observee but also the observed properties of them are dynamic. May Apple save me (and you?).

I mean, how to rock and rotate interfaces in your UIKit based apps.

Apple taught me most I need to know about how to manage the interface orientation, but still left some dark corners that I had to explore by myself. Now that I’ve seen the whole landscape, I want to share it with you.

Read the documentation first if you haven’t yet. After that, you should know how to write the rotation code to respond to orientation changes, if only you are notified of the orientation changes in the first place.

Your view controller is always notified of the orientation changes if it is the frontmost view controller – the only view controller, the top modal view controller, the top view controller in the top navigation controller, or the current selected view controller in top tab bar controller. In these cases, simply following the documentation by implementing your rotation logic in those view rotation methods ^(willRotateToInterfaceOrientation:duration:, willAnimateRotationToInterfaceOrientation:duration:, and didRotateFromInterfaceOrientation:)$ is enough.

However, no view rotation message will be sent to your view controller if the rotation occurs when it is not in the frontmost. Well, it is very reasonable behavior though, since its view is invisible then. Laziness is a great virtue here. What’s the point of rotating the invisible view under the hood except for consuming more battery, especially considering that the interface may be rotated back to its original orientation? What makes it a problem is the fact that these messages will neither be sent to your view controller when it becomes the frontmost one later. Your view controller will be never aware of the orientation changes that happen when it is not in the frontmost! One example for better understanding:

1. A is the current selected view controller in a tab bar controller and the device is in portrait orientation.
2. View controller B is selected in the tab bar controller.
3. The device is rotated to landscape orientation.
4. A is selected again.

See the problem? The orientation is portrait at first, and view controller A presents its view correctly; the orientation becomes landscape later, but A does not know that and still presents a portrait view when it returns to the frontmost.

In fact, the example could be reduced to a simpler one:

1. B is the current selected view controller in a tab bar controller and the device is in portrait orientation.
2. The device is rotated to landscape orientation.
3. View controller A is selected.

The example can be easily extended to view controllers managed by a navigation controller. ^(The situation of modal view controllers is different. The rotation messages will be properly sent to the concerning view controllers. I don’t know why Apple can’t treat them the same way.)$ The problem is reduced to: view controller A initially sets up its view in portrait mode and relies on the code in view rotation methods to adjust the view to new orientations, but view rotation messages are never sent to A so it never rotates its view.

It is clear now that not only view rotation methods should have code for adjusting view for different orientations, but also the initial view setting up code should be orientation dependent. And that’s Apple didn’t tell us.

Finally, here is my way to attack this problem:

• Factor the orientation-dependent layout code into a method, naturally called (void)layoutView:(UIInterfaceOrientation)orientation.
• Call layoutView: in both viewWillAppear: and willAnimateRotationToInterfaceOrientation:duration:.

May this article help you rotate your apps nicely and may your apps rock.

Documentation set generation tool in Xcode to generate documentation sets in the style of Apple Developer Documentation is necessary for a prosperous Apple developer community. The current HeaderDoc and Doxygen are both far from Apple standard.

HeaderDoc is obviously not favored by developers. Doxygen is better and even officially advocated by Apple, but still tedious to use and just can’t generate Apple standard documentations(see a nice example here). Doxyclean is very helpful in converting Doxygen output to resemble Apple Developer Documentation, but seems not capable to generate Xcode Documentation Sets. Following the work of Doxyclean, appledoc supplements some missing features like Xcode Documentation Set generation.

To sum up, there are several third-party tools doing the work that should be better done by Apple in Apple way. Even though they can do their best to generate very Apple like documentations, they can not offer the smooth integration in Xcode that is otherwise possible if it is done by Apple.

So, I’ve posted a bug report(Problem ID: 8193210) to request such a Documentation Set generation tool. If you also want it, please go to duplicate a bug report with following content:

I vote for bug report ‘8193210′.

Summary:
Documentation set generation tool in Xcode to generate documentation set in the style of Apple Developer Documentation is necessary for a prosperous Apple developer community. The current HeaderDoc and doxygen are both far from the Apple standard.

Steps to Reproduce:

Expected Results:

Actual Results:

Regression:

Notes:

Read this article to learn why and how to vote for a bug report. ^(Surely I’ve voted this “international promo codes” bug report since I’m from China.)$

The Android API for querying SQLite databases supports two styles of queries:

1. query(uri, projection, selection = "column=" + value, selectionArgs = null, sortOrder)
2. query(uri, projection, selection = "column=?", selectionArgs = { value_as_string }, sortOrder)

Obviously, the first one is more straightforward and convenient. Then what’s good about the second one?

Let me try to sell the goodness of selectionArgs via a simple example.

Suppose you are querying contacts with phone number, say, “+8612345678901″. With the first style, you get the WHERE clause "number=+8612345678901" which is the result of string concatenation ‘"number=" + "+8612345678901"‘.

It is easy to see that phone numbers are not pure numbers, i.e., they are not numeric. For example, the number “(010) 87654321 ” and “010-87654321-001″, are valid phone numbers, but are neither valid integer nor real numbers ^(Of course, you don’t want to do the subtraction of the latter.)$. Thus, the the type of the number column (storage class in SQLite’s idiom) is TEXT.

From this nonnumeric phone number string raises a problem, a quite subtle one. With its dynamic type system、column affinity and type conversion, SQLite will try to convert “+8612345678901″ to a text string. But the express “+8612345678901″ is numeric originally, because it has no quote marks surrounding it, and numeric values are operated according numeric rules first. So it is first normalized to “8612345678901″, and then the normalized value is converted to a text string “‘8612345678901‘“.

So the query that is really fed into the SQLite engine is something like this:

But as a text string, ’8612345678901′ can not be matched with ‘+8612345678901′, and the query fails.

We were suffering this kind of adversity until selectionArgs came to save the day.

With the second style, Android SQL query builder will replace ?s in selection with the values from selectionArgs, in order that they appear in the selection. The values must be String and will be treated as text strings by SQLite, i.e., they must be converted to their String representation first if they are not String, and will be quoted automatically when replacing the ?s. So the query that is fed into the SQLite engine is something like this:

At this point, it doesn’t matter whether the underlying column type is really TEXT or not, because whatever the TEXT value is derived from, it can be correctly cast back to the original column type. The key point is that TEXT can be losslessly converted to any other types, but not necessarily vice versa as shown above.

In fact, we can stick to the first style by manually simulating the works done by Android SQL query builder this way:

But as you can see, it is such a tedious concatenation with just one query column, you don’t want to imagine the mess with more complex queries, do you?

For last several weeks, I’ve been struggling to intercept (not only get notice of) incoming calls on Android, but finally I have to admit that I failed.

Actually, I’m doomed to fail, because it is just Mission Impossible.

For the time being, a BroadcastReceiver for "android.intent.action.PHONE_STATE" is the only chance for application developers to generally probe for incoming calls. However, it comes too late.

Here is why.

com.android.internal.telephony.gsm.RIL.RILReceiver.run():                                               +---+ 
                                       android.net.LocalSocket.getInputStream() <-----------------------|   |
                                                                  /                                     |   |
                                                                 |                                      |   |
                                                                 v                                      | R |
  com.android.internal.telephony.gsm.RIL.readRilMessage(InputStream, byte[])                            | A |
  com.android.internal.telephony.gsm.RIL.processResponse(Parcel):                                       | D |
  Case 1: Unsolicited Commands - Incoming Call                                                          | I |
    com.android.internal.telephony.gsm.RIL.processUnsolicited(Parcel)                                   | O |
    com.android.internal.telephony.BaseCommands.mCallStateRegistrants.notifyRegistrants(AsyncResult)    |   |
    com.android.internal.telephony.gsm.CallTracker.sendMessage(Message)                                 |   |
                                                        |                                               |   |
                                                        |                                               | S |
                                                        v                                               | Y |
    com.android.internal.telephony.gsm.CallTracker.handleMessage(Message)                               | S |
    com.android.internal.telephony.gsm.CallTracker.pollCallsWhenSafe()                                  | T |
    com.android.internal.telephony.gsm.RIL.getCurrentCalls(Message)                                     | E |
    com.android.internal.telephony.gsm.RIL.send(RILRequest)                                             | M |
                                                     |                                                  |   |
                                                     |                                                  |   |
                                                     v                                                  |   |
    com.android.internal.telephony.gsm.RIL.RILSender.handleMessage(Message)                             |   |
                               android.net.LocalSocket.getOutputStream().write(byte[]) ---------------->|   |
                                                                                                        +---+    
  Case 2: Solicited Commands - Request Call Info
    com.android.internal.telephony.gsm.RIL.processSolicited(Parcel)
    com.android.internal.telephony.gsm.RIL.findAndRemoveRequestFromList(int)
    com.android.internal.telephony.gsm.RILRequest.mResult.sendToTarget()
                                                           |
                                                           |
                                                           v
    com.android.internal.telephony.gsm.CallTracker.handleMessage(Message)
    com.android.internal.telephony.gsm.CallTracker.handlePollCalls(AsyncResult)
    com.android.internal.telephony.gsm.GSMPhone.notifyNewRingingConnection(Connection)
    com.android.internal.telephony.PhoneBase.notifyNewRingingConnectionP(Connection):
      com.android.phone.CallNotifier.sendMessage(Message)
                                           |
                                           |
                                           v
      com.android.phone.CallNotifier.handleMessage(Message)
      com.android.phone.CallNotifier.onNewRingingConnection(AsyncResult)
      com.android.phone.PhoneUtils.showIncomingCallUi() <---------------- Users see incoming call
 
    com.android.internal.telephony.gsm.CallTracker.updatePhoneState()
    com.android.internal.telephony.gsm.GSMPhone.notifyPhoneStateChanged()
    com.android.internal.telephony.DefaultPhoneNotifier.notifyPhoneState(Phone)
    com.android.server.TelephonyRegistry.notifyCallState(int, String)
    com.android.server.TelephonyRegistry.broadcastCallStateChanged(int, String) <--- Too late to interfere

DreamHost provides a snapshot backup service. However, this backup service seems a little shabby:

You may request a backup once every 30 days.

Due to some technical limitations, any users or databases greater than 4GB will not be included in these backups!

We also recommend that you maintain your own off-line backups locally.

Of course, they should complement such a faint backup service with something. It turns out that they do. DreamHost offers one Backups User per account (I’ll simply call it DreamHost Backups):

At DreamHost, you may only keep website-related content on your regular users.
You do, however, get one user per account where anything legal may be stored; your Backups User.

This user cannot have any websites pointed to it, nor may you share files via it… it is only to be used as an off-site backup for your personal files.
As such, we keep no backups of files on this account. These are already supposed to be your backups… not your only copy!
(Of course, you should always keep your own copies of all data stored with us.. we make no guarantees!)

Every full DreamHost Hosting plan includes 50GB of backups space!
(Additional usage will be charged at the rate of 10 cents / GB a month: the best backup deal on the net!)

You may access your backup user via ftp, sftp, scp, and rsync!

Surely, anything legal includes your legal web sites on DreamHost. And 50GB, in my opinion, is large enough for personal or small business web sites ^(If you are running web sites larger than 50GB, I’m sure you know everything I’m talking about here much better than me, so this article is obviously not for you.)$. So why not a meta backup of your DreamHost web sites on DreamHost Backups? ^(Notice that DreamHost Backups are hosted on different servers from web hosting servers, which makes much more sense for our meta backup.)$

Let’s just do it. I’m sure to get your hands dirty along the way. So be warned before reading on.

Mainly, I grabbed the pith from the clever Snapshot-Style Backups:

rm -rf backup.3
mv backup.2 backup.3
mv backup.1 backup.2
rsync -a --delete --link-dest=../backup.1 source_directory/  backup.0/

The core application used is rsync which is fortunately supported by DreamHost Backups.

But to incrementally build multiple versions of snapshot, only rsync is not enough. We also need at least two other shell commands: mv and rm.

Neither of them is available due to the lack of shell support on DreamHost Backups. What we have are only ftp, sftp, scp, and rsync, remember?

So, what we can do now is just make good use of what we have. In fact, we’ll need to make extreme use of two of them.

rsync is one. Which is the other one? scp can be first eliminated, for copy is already perfectly handled by rsync. Between the left two, I’ll take the safe side. So, sftp.

All ftp clients can do renaming, they just rename mv rename (quirk intended). To our great joy, sftp support batch mode, which means we can put all the renames in a script, and feed it to sftp which then cranks at it dutifully without any further interfere from us.

rm is the only knot left, which turns out to be a really hard one.

sftp supports rm, but only for files; it also supports rmdir, but only for empty directories. What we need is recursive rm ^(lftp supports recursive rm though not very smoothly; besides, it is not pre-installed on DreamHost.)$, and we are going to simulate one, by rsync, of course.

NOTICE: this is the only valuable part of this fluff, so attention please.

rsync -avz --delete --include='/backup.3' --exclude='/*' any_source_dir_without_backup.3 backups_user@backups_host:path

It is mind-boggling, I know. So let me explain it:

• “–delete” — to delete the missing files/directories from destination;
• “–exclude=’/*’” — to skip all files/directories when comparing source and destination, except for;
• “–include=’/backup.3′” — the one to be deleted, must be put before the exclude-all clause, otherwise it would be excluded first and have even no chance to be checked for whether it should be included;
• because “–delete” has effect only for the missing part, ‘/backup.3′ must be missing at source.

Another point maybe of interest is that you’d better make a proper filter for rsync to use when syncing. It will save you both bandwidth and disk space.

I exclude my locally installed softwares (~/bin, ~/include, ~/lib, ~/share, ~/var), sensitive information (~/.ssh/, ~/.my.cnf; actually, I exclude all dot files under my home directory, i.e., ~/.*, since it is web sites not development host that are being backed up), and other stuffs that just make no sense to be backed up, like source packages of the softwares (~/soft), temporary swap files of Vim (*.swp), and backup files spewed by Emacs (*~). I put all these exclusive filter rules in a script and feed it as the value of the ‘–exclude-from’ option to rsync.

That’s all. All the other utilities, such as mysqldump for mysql backup, and cron for scheduled automatic backup, are all explained very clearly on wiki.dreamhost.com.

Lastly, I’ll wrap all these up into several scripts (assumed to be put in ~/backup_utils), for you to take away:

# Remember to make it executable, via "chmod +x ~/backup_utils/mybackup".
 
# dump mysql: the password is stored in ~/.my.cnf which is not to be backed up for security
mysqldump -u mysql_user -h mysql_host -A >| mysql_dump_path
 
# rsync and sftp both use ssh whose keys are stored in ~/.ssh/ which is not to be backed up for security
# delete the oldest
rsync -avz --delete --include='/backup.3' --exclude='/*' any_source_dir_without_backup.3 backups_user@backups_host:path
# rename olds to olders
sftp -b ~/backup_utils/sftpcmds backups_user@backups_host:path
# send the new
rsync -avz --exclude-from="$HOME/backup_utils/rsync.filter" --delete --link-dest='../backup.1' ~/ backups_user@backups_host:path/backup.0/

rename backup.2 backup.3
rename backup.1 backup.2
rename backup.0 backup.1

/bin/
/include/
/lib/
/libexec/
/share/
/soft/
/var/
/.*
*~
*.swp

# daily backup
0 0 * * * ~/backup_utils/mybackup

PS: While I am writing this article about DreamHost backup, my backup script is backing up drafts of the article. What a meta backup!

Not American. Not British.

You know what I am saying if you’ve read Jeff Atwood’s The Ugly American Programmer

As a programmer from China, I’m humble and excited to see so many comments concerning Chinese on that post. I’m also amazed to see a Chinese clone of Stack Overflow, which I think should be applauded and encouraged. ^(Do you think so, Jeff?)$

IMO, there is a strong correlation between English mastery and programming competence among Chinese programmers.

It’s no to say that all good Chinese programmers always prefer English in tech areas, but that they all have the ability to some extent to read, write, and talk (the three abilities in descending order) tech things, in English.

And I dare say that the top 5% of Chinese programmers do prefer English docs over translated ones, which is easy to understand. The top programmers are clever enough to grasp English well enough, so well that they are no worse interpreters than the translators of the docs, at least to themselves. In fact, reading is just first half of translating, and of course easier to be done well.

Translation is not a direct mapping or table-looking-up, but is a more sophisticated indirect process. Suppose I, a Chinese, am reading a paragraph of English text. The original language, English, is the input, the target language, Chinese, is the output, and I am the processor. I grab the input, and the English workshop of my language center crunches out the meanings, save them in some temp areas of my brain, during which the Chinese workshop may or may not be involved. By then, I understand the text, and the reading is done. Suppose now I am translating the text. I pick up the meanings produced in the first phase, and throw them to the Chinese workshop which organizes Chinese sentences around the meanings. By then, I can give out the output, and the translating is done. You see, translating is composed of two phases, understanding and reorganizing. The reorganizing part is much more difficult, since we all have those moments that even though we sense it, we are just not able to express it (只可意会，不可言传). Luckily, reading only involves the first part.

However, I believe the top Chinese programmers still stick to Chinese in oral communication, though with quite a lot sprinkles of English words. They talk in Chinese because they speak it everyday. When one can express himself better in his mother tongue, why should he laboriously lisp in English? Just to practice or show off (装13)? They mix in English words because maybe those words have no good correspondence in Chinese, or are just felt more natural than their Chinese counterparts, or only because the speakers have never thought of the Chinese way of saying them, since they learn them from English docs.

I’m sorry if some Chinese programmers feel I’m an arrogant ass or 崇洋媚外 or even both, when I say top programmers likes English docs. I’m not saying that one can not be a top programmer without mastering English, but I do believe it is much harder since one is severely handicapped when the dominance of English in IT resource is status quo. After all, it is Information Technology we are talking about. What do you think it means to an IT engineer when his information is delayed or even tampered?

Let’s face it. To us Chinese programmers, there is a gap along the English-Competence axis, splitting us into two groups. There is a higher probability to be top programmers in the Good-At-English group than in the Poor-In-English group. If you are a good programmer with great potential squatting in the latter, please help us to move yourself to the former, then China will have a slightly better chance to lead in IT industry for so many of you with a higher probability to exploit your programming potential. But it is just probability, you can be masculine and bet against it. I hope you not.

I’ve been planning to do something to help fill the gap from the very beginning of this blog. So I’ve intentionally writing Chinese and English posts alternatively. A better and more ambitious way is to write some of them in both Chinese and English, so those not so good at English can try to read the English version first, and refer to the Chinese version occasionally when unsure. I have the faith that this format of bilingual posting is more approachable for Chinese programmers intent on improving English, if only I have the willpower to do so and the necessary stuff to entice those programmers. I will try.

我替你擦屁股，你还嫌纸糙。
那我问你，这坨到底是干啥的？

你说这是历史。

我当然知道这是屎，不然我费这劲来善你的“后”？

不好意思，我这么说你可能听着刺耳。
可你留的这坨 ASCII 码，不但闻着刺鼻，看着刺眼，连想着都恶心。

Problem: What’s the probability that at least one run of k consecutive heads occurs in n coin tosses?

Definitions:

• R{k,n}: the fact that at least one run of k consecutive heads occurs in n coin tosses.
• ~E: the fact that event E does not occur.
• A & B: the fact that event A and event B occur simultaneously.
• P(E): the number of permutations that cause event E to occur.
• H(k,n): the number of head-or-tail permutations for n coins that contain at least one run of k consecutive heads; the same as P(R{k,n}).

Theorem:

P(A & B) + P(A & ~B) = P(A)

Analysis:

If n = k, R{k,n} occurs in exactly once case, so H(k,n) = 1.

If n < k, R{k,n} is impossible, so H(k,n) = 0.

Otherwise(n > k), H(k,n) permutations can be divided into two groups: (a) R{k,n-1}, and (b) ~R{k,n-1}.

1. R{k,n-1}

   R{k,n} follows necessarily. There are 2H(k,n-1) permutations of this kind.

2. ~R{k,n-1}

   R{k,n} occurs only if the last k-1 of the first n-1 toss are all heads and the nth toss is head. Then the kth last toss of the first n-1 tosses must be tail, otherwise the last k of the first n-1 tosses are all heads, which contradicts ~R{k,n-1}. Hence, the last k+1 tosses are fixed as [T,H,H,...,H].

   Definition:

   • S: the fact that the last k+1 tosses of n tosses are [T,H,H,...,H].

   The condition now turns out to be ~R{k,n-1} & S, which is equivalent to ~R{k,n-k-1} & S. Thus the permutation number is

   P(~R{k,n-k-1} & S) = P(S) – P(R{k,n-k-1} & S) = 2^(n-k-1) – H(k,n-k-1).

Thus,

• H(k,n) = 2H(k,n-1) + 2^(n-k-1) – H(k,n-k-1), for n > k;
• H(k,n) = 1, for n = k;
• H(k,n) = 0, for n < k.

A cool method using probability distribution vector and probability distribution transition matrix. The original post is in Chinese. I am trying to translate it into English below. The author even proved the property used in Method Three along the line; however, this part is beyond my knowledge.

The states during the process of coin tossing is defined as follows:

• S_t(0 ≤ t < k): no runs of k consecutive heads have occurred, and t heads have accumulated in the last run.
• S_k: at least one run of k consecutive heads has occurred.

Lemmas:

• The initial state is S₀.
• If current state is S_t(0 ≤ t < k), next state has equal opportunity, i.e.1/2, to be S_t+1 or S₀.
• Once state becomes S_k, it will never change again.

Definition:

• d_i: the probability distribution vector after the ith toss is a column vector of length k+1, whose hth element is the probability that current state is S_h-1.

Initially, d₀ = [1;0;0;...;0]; d_i+1 = M ⋅ d_i, wherein M is the probability distribution transition matrix.

M can be reduced from lemmas above:

Thus, the last element of d_n is the probability desired, denoted as P.

P = [0,0,...,0,1] ⋅ d_n = [0,0,...,0,1] ⋅ Mⁿ ⋅ d₀.

Use the fact “the probability that no runs of consecutive tails will occur in coin tosses is given by , where is a Fibonacci -step number” from mathworld.wolfram.com/CoinTossing.html.