http:^^www.cs.washington.edu^homes^jbaer^layers.html

来自「This data set contains WWW-pages collect」· HTML 代码 · 共 375 行 · 第 1/2 页

If lcc's checking of level boundaries succeeds, then it outputs
intermediate .c files with the annotations stripped out and execs cc
or gcc on those files.  This approach has the advantage that it brings
support for layers closer to the language level.  The disadvantage
with this approach at the moment stems from the fact that lcc does not
contain a full C parser.  Thus, syntax errors may confuse lcc, causing
it to output layer-related errors without telling you about the syntax
errors.  In fact, in this case it will never actually produce
intermediate files on which to run a real compiler, so the programmer
will essentially be stuck with trying to find the error by hand or
removing all annotations and compiling, neither of which are
satisfactory solutions.

<p>
The second approach, which has neither the advantages or disadvantages
of the first is to view lcc as an optional static checker.  In this
version of lcc, levels are specified as annotations enclosed in C
comments.  They still utilize the @level keyword and live in the same
place in the source code, but since they are in a comment, the source
code can still be compiled using a regular C compiler.  In this
approach, the example above now looks like:

<pre>
int foo(double x) /* @level 3 */
{
    <i>function body</i>
}
</pre>

<p>
lcc performs the same basic analysis, except that it now must locate
these particular comments (since it normally skips all comments) to
find the annotations.  While the version of lcc using this second
approach is currently much more usable than the version implementing
the first approach, it is the author's belief that bringing layer
support closer to the language level (as in the first approach) is
ultimately more desirable, given the addition of a complete C parser
(with the addition of the @layer syntax) to lcc.



<p><br><p>
<b>Layered C Extractor (lce)</b>
<p>
lce is similar to lcc in that it checks C source code to see if the
boundaries between levels are maintained.  However, rather than using
source annotations to determine the level to which a function is
assigned, lce will automatically generate the mapping of functions to
levels.  Thus, lce is perhaps more applicable to the process of
reverse engineering or program understanding than to a forward
engineering process.  The same options for recursion, invocation layer
crossing thresholds, etc. from lcc are available in lce.

<p>
lce works by first extracting a call graph from the source in the same
manner as lcc.  It then performs a recursive depth-first search of the
call graph, starting at main.  A level counter is incremented at every
level of recursion, and if a function is called from the current
level, the level of the that function is set to 1 + the current level,
as long as it is not already deeper.  Note that lce assigns levels in
an inverted order as that normally accepted by lce.  Namely, main() is
at level 0, and functions lower in the hierarchy are at higher
numbered levels.  lcc can optionally use this same "inverted" layer
ordering, but lce uses it exclusively.

<p>
Performing a depth-first search of the call graph does yield one
possible assignment of layers -- namely that assignment in which each
function gets assigned to the highest possible layer in the hierarchy.
This may not, however, be the optimal assignment of layers.  One might
imagine, for example, that a desirable scheme for mapping functions to
layers would be to minimize the number of layers crossed by any
invocation.  Rather than addressing this in the algorithm itself,
however, an approach inspired by the reflexion models [MNS95] was taken.
lce was modified to recognize the @level annotations used by lcc.
This allows the user to set the levels of certain functions "in stone"
with an annotation, and then see if the desired level boundaries are
maintained.  lce fixes only the level of the functions which are
annotated, and still uses a depth-first search to map levels to the
rest of the functions.  

<p>
Following are two sample executions of lce, once on itself, and once
on the source for the UNIX command agrep.  As it turns out, neither of
these programs have a strict layered invokes structure.  No invokes
hierarchy exists for agrep in which no invocations cross less than 4
level boundaries.  With allowable layer crossings set to 3, there was
one offending invokes.  To test whether this 4 layer crossing was
truly necessary, the calling function was annotated to be fixed at one
level lower than the depth-first search had placed it.  However, when
the test was re-run, the 4 layers of separation between these two
functions remained.  The agrep example also illustrates another
capability of lce which is a side effect of depth-first searching on
the call graph.  If a function or functions are never visited during
the depth-first search, it may be that they are never called and lce
flags this possibility.

<pre>
898 cindy:layered_c >lce -l -r lce.cc
Functions by level:
level 0
    lce.cc: main
level 1
    lce.cc: FindFunctions
    lce.cc: FindCallgraph
    lce.cc: AssignLayers
    lce.cc: CheckLayers
level 2
    lce.cc: AssignLayersDFS
    lce.cc: AddToFnList
    lce.cc: nextTokenStr
level 3
    lce.cc: HandleError
    lce.cc: FunctionLookup

lce.cc: Illegal level crossing:
    FunctionLookup (level 3) invoked from FindCallgraph (level 1)
lce.cc: Illegal level crossing:
    FunctionLookup (level 3) invoked from FindCallgraph (level 1)
lce.cc: Illegal level crossing:
    FunctionLookup (level 3) invoked from AssignLayers (level 1)
lce.cc: Illegal level crossing:
    HandleError (level 3) invoked from AssignLayers (level 1)
lce.cc: Illegal level crossing:
    FunctionLookup (level 3) invoked from CheckLayers (level 1)
lce.cc: Illegal level crossing:
    FunctionLookup (level 3) invoked from CheckLayers (level 1)
Exiting with errors 

899 cindy:layered_c >lce -4 -r ../hw5/agrep2.04/*.c
A layered invokes structure exists which satisfies the input constraints!

Note: as far as lce can tell, the following functions will
never be invoked (though they may be through function pointers):
    ../hw5/agrep2.04/utilities.c: subset_pset
    ../hw5/agrep2.04/utilities.c: eq_pset

</pre>

<p><br><p>
<b>Future Work</b>
<p>
Few concrete conclusions can be drawn at this point about the
usefulness of these tools, as they have yet to be used for any real
software engineering project.  The purpose of this paper however, has
been simply to provide some motivation for tools to support the
development of layered systems, and describe some of the author's
early attempts at building such tools.

<p>
There are several directions in which future work would be beneficial.
The most important direction would be to actually try building some
non-trivial size programs with a layered design using lcc.  Only by
doing this will any real measure of the value of these tools be
attainable.  Some other interesting possibilities for future work
include:

<ul><li>
Extend lcc to include a full C parser
</li><li>
Explore the support of layers for other languages (particularly those
that already provide support for a greater degree of structure than C)
</li><li>
Explore other ways of grouping layer designations in source code
</li><li>
Improve the search capabilities of lce to look for more optimal
layerings than those obtained from simple depth-first search.
</li></ul>


<p><br><p>
<b>References</b>
<p>
[P72] D. L. Parnas.  On the Criteria To Be Used in Decomposing
Systems into Modules.  <i>Communications of the ACM</i>, 1053-1058,
December 1972.
<p>
[P79] D. L. Parnas.  Designing Software for Ease of Extension and
Contraction.  <i>IEEE Transactions on Software Engineering</i>,
SE5(2):128-138, March 1979.
<p>
[MNS95] Gail C. Murphy, David Notkin, and Kevin Sullivan.  Reflexion
Models: Bridging the Gap between Source and High-Level Models,
<i>ACM SIGSOFT Software Engineering Notes</i>, 20(4):18-28, October 1995.

</body>
</html>